{"id":"arxiv/2610.09972","url":"https://arxiv.org/abs/2610.09972","tags":["cs.DS","cs.CC","math.CO"],"score":0,"title":"A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs","domain":"cs.DS","source":"arxiv","authors":["Zhiqiang Xu"],"reviews":0,"subject":"cs.DS","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-07","reactions":{}}