Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper presents a deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs, achieving an operator norm bound of strictly less than $2\sqrt{Δ-1}$ for graphs with maximum degree $Δ\ge3$. The algorithm deterministically selects signs and prunes vertices, building upon the randomized recursive repair framework. This resolves a long-standing open problem in spectral graph theory and theoretical computer science.
Deterministic polynomial-time algorithm finally cracks the Bilu--Linial signing problem, achieving the tight Ramanujan bound for bipartite graphs.
We give a deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs. For every finite simple bipartite graph of maximum degree at most an integer $Δ\ge3$, the algorithm assigns signs to its edges so that the signed adjacency matrix has operator norm strictly less than $2\sqrt{Δ-1}$. Our algorithm builds on the randomized recursive repair framework of Jadbabaie, Saberi, and Sra~\cite{JSS26}, with deterministic rules for sign selection and vertex deletion.