arXiv:2610.09972 · v3

A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs

首次提交 2026-10-07 20:40

版本更新 2026-10-26 09:33

雷达观测 2026-10-29 00:36

摘要

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.

作者备注：20 pages. We have improved the presentation and clarified some details of the arguments