CS Paper Radar

Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time

Ali Jadbabaie, Amin Saberi, Suvrit Sra

cs.DS math.COmath.FAmath.OC ·submitted 2026-09-20 20:21 UTC · v1
theory

Abstract

We prove two main algorithmic results in spectral discrepancy. First, we give a deterministic polynomial-time rounding theorem for rational positive semidefinite matrices of arbitrary rank. The algorithm starts from any rational fractional signing and assigns one sign per original matrix. Its discrepancy is less than $3.37\,\|\sum_i \mathrm{Tr}(A_i)A_i\|^{1/2}$. This yields Kadison--Singer half-partitions with error below $1.69\sqrt{\varepsilon}$, as well as deterministic graph signings that control signed adjacency and signed degrees simultaneously. The proof builds on the spectral-potential method of Ezeunala and Jiang (2026) and introduces a new way to choose rounding directions. We prove polynomial bit complexity for the rounding procedure. Second, we give a Las Vegas algorithm for the Bilu--Linial signing problem on an arbitrary prescribed graph. If $G$ has $n$ vertices and maximum degree $Δ\ge3$, the algorithm terminates almost surely. It uses fewer than $100n^3$ insertion attempts in expectation and returns a signing with $\|A_s\|<2\sqrt{2(Δ-1)}$. For bipartite graphs its one-sided form gives the sharp universal bound $\|A_s\|<2\sqrt{Δ-1}$. The algorithm builds the signing by inserting vertices and recursively deleting and restoring neighbors after rejected insertions. In the analysis, the $\sqrt2$ gap to the Bilu--Linial conjecture comes from a factor of two in the bound for vertex deletions in the two-sided case. On a $d$-regular bipartite Ramanujan base the same signing produces a Ramanujan $2$-lift of that prescribed base.

Comment
Sharing early for feedback. Exposition is being improved for the next revision. Github for certificates will be made available in the near future

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS cs.CCmath.CO ·2026-10-07 ·Zhiqiang Xu
similarity 0.72
Abstract · 20 pages. We have improved the presentation and clarified some details of the arguments

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.

0.36

Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials

cs.DM math.CO ·2026-09-14 ·Fangfang Lin, Hong Zhou
theory similarity 0.70
Abstract · 25 pages, slightly improved bound for graphs of girth at least 5, include some recent progress

Bilu and Linial conjectured that every finite $d$-regular graph with $d \geq 2$ admits an edge signing $σ$ whose signed adjacency matrix $A_σ$ has spectral radius at most $2\sqrt{d-1}$. We prove that every signing meeting the mixed-root condition $r_{A_σ}\leq\sqrt{2(d-1)}$ satisfies \[ ρ(A_σ) < \frac{3+\sqrt5}{2}\sqrt{d-1}, \] where $r_{A_σ}$ is the largest root of the mixed determinantal polynomial $χ[A_σ,-A_σ]$. The interlacing theorem of Ravichandran and Srivastava guarantees a signing satisfying the mixed-root condition, so our result improves the coefficient $2\sqrt2$ in their two-sided spectral bound. In the proof, we construct a positive matrix-valued probability measure supported on the roots of $χ[A_σ,-A_σ]$. The second moment gives a simple matrix inequality $A_σ^2 + dI \preceq 4r_{A_σ}^2I$, which yields a preliminary coefficient $\sqrt{7}$. Estimates for the fourth moment use information about short walks to obtain the coefficient $(3+\sqrt{5})/2$. For triangle-free graphs, the coefficient improves to $\sqrt6$, and for graphs with girth at least five, it improves to $\sqrt{35/6}$. As a result of independent interest, we extend the construction to $χ[A_1,\ldots,A_k]$ for Hermitian matrices $A_1,\ldots,A_k$ with zero diagonal, and compute the first two moments explicitly. Finally, an explicit signing of $K_8$ shows that the mixed-root condition alone cannot guarantee a coefficient below $(4+\sqrt5)/\sqrt6$.

0.55

A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture

cs.DS math.FA ·2026-09-16 ·Tarun Kathuria
similarity 0.70
Abstract · The author explicitly reserve all rights in this work. No permission is granted for the reproduction, storage, or use of this document for t…

\cite{mss2015} proved Weaver's discrepancy result existentially, resolving the Kadison--Singer conjecture . Finding such signs efficiently for general inputs remained an open algorithmic question. In the real-arithmetic model, we give a deterministic algorithm running in polynomial time with discrepancy at most $35\sqrt\varepsilon$. The algorithm walks from the origin of the hypercube to a vertex, fixing coordinates as they hit a face. Its potential measures a soft spectral edge of the discrepancy matrix perturbed by an operator-valued free semicircular element. The perturbation's covariance vanishes as the coefficients reach their endpoints. Inspired by the free interpolation approach of Bandeira, Boedihardjo, and van Handel \cite{bbvh2023}, we combine Lehner's variational formula \cite{lehner1999} with spectral Tsallis--$1/2$ regularization used in \cite{allenZhuLiaoOrecchia2015} and \cite{pesentivladu2026}. The resulting potential has a finite-dimensional SDP formulation, allowing the discrepancy and remaining covariance to be analyzed together. We analyze the optimizer's stability through the linearized Karush--Kuhn--Tucker (KKT) system of a regularized min--max problem, whose stationarity equations are related to the matrix Dyson equation \cite{erdos2019}. This gives the movement rule: either a coordinate can move toward its nearer endpoint at small spectral cost, or a low-curvature direction orthogonal to the current coefficient vector allows further progress. Choosing the better sign of this direction controls discrepancy while increasing the squared distance from the origin. Upcoming work \cite{kathuria2026higherRank} will address higher-rank Kadison-Singer and spectrally thin trees. Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.

0.56

A Walk From Free Probability to Matrix Discrepancy III: Higher Rank Kadison-Singer and Spectrally Thin Trees

cs.DS ·2026-09-18 ·Tarun Kathuria
theory similarity 0.69
Abstract · The author explicitly reserve all rights in this work. No permission is granted for the reproduction, storage, or use of this document for t…

Let $A_1,\ldots,A_N$ be positive semidefinite matrices of rank at most $r$, with $\sum_i A_i=I$ and $\norm{A_i}\le\varepsilon$. We prove that one sign can be assigned to each original matrix with discrepancy $O(\sqrt{\varepsilon\log(2r)})$, independently of their dimension and number, which is known to be optimal upto constants. We give a separate existence proof and a deterministic algorithm with polynomial work in a real-arithmetic model with semidefinite-value and exact spectral primitives. Separate Lean formalizations verify the existence proof and the algorithm in this arithmetic model. The proof extends the variational approach to discrepancy developed in the companion papers, motivated by operator-valued free interpolation, Lehner's formula, and spectral Tsallis regularization. A concave matrix power interpolates between a trace source and a sandwich source. Its concavity controls the response of the optimizing density. The walk maintains independent source reserves and a second matrix recording reserve expenditure. This matrix certifies contraction of the unfinished input mass between epochs; within an epoch, preparation and a negative-curvature step control the spectral potential while the coefficients advance toward signs. As applications, one spanning tree can be chosen simultaneously $O(\varepsilon\log(2s))$-spectrally thin for $s$ positive weightings of a common graph whose edge leverages are at most $\varepsilon$. The diagonal specialization gives discrepancy $O(\sqrt{L\log(2k)})$ for matrices with row sums at most $L$ and at most $k$ nonzero entries per column, through a walk of fractional colorings.

0.38

Polynomial Time Algorithms for the Kadison-Singer Problem

cs.DS ·2026-09-17 ·Zhao Song, Song Yue
hot direction similarity 0.66
Abstract

Marcus, Spielman, and Srivastava [MSS15] established the existence of Kadison--Singer partitions. We provide polynomial-time algorithms for the Kadison--Singer problem. For Hermitian matrices $A_1,\ldots,A_m\in\mathbb C^{n\times n}$ of rank at most one, we give two algorithms that find signs $σ\in\{\pm1\}^m$ satisfying $\|\sum_i σ_iA_i\|\le C\|\sum_i A_i^2\|^{1/2}$. The deterministic algorithm achieves $C=3.3443$ using $\widetilde O(mn^2+n^{4.75})$ arithmetic operations. The randomized algorithm achieves $C=4.8628$ using $\widetilde O(mn^2+n^{3.58})$ arithmetic operations in expectation. For vectors satisfying $\sum_i a_ia_i^*=I$ and $\|a_i\|^2\leα$, the algorithms yield partitions $[m]=I_1\cup I_2$ satisfying $\|\sum_{i\in I_j}a_ia_i^*-I/2\|\le (C/2)\sqrtα$ for $j=1,2$.

0.45

Kadison--Singer in Deterministic Polynomial Time

cs.DS cs.DMmath.COmath.FA ·2026-09-15 ·Ekene Ezeunala, Haotian Jiang
hot direction similarity 0.65
Abstract

We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices $H_1,\dots,H_N$ of rank at most one, finds signs $s\in\{\pm1\}^N$ with $\|\sum_i s_i H_i\|\le 13\|\sum_i H_i^2\|^{1/2}$. As a corollary, for vectors $v_i$ with $\sum_i v_iv_i^*=I$ and $\|v_i\|^2\leδ$, the signs yield a partition $[N] = S_1 \cup S_2$ such that each part satisfies $\|\sum_{i \in S_j} v_i v_i^* - \frac{I}{2}\| \leq \frac{13}{2}\sqrtδ$ for $j = 1,2$. This gives a deterministic polynomial-time algorithm for the Kadison--Singer problem, in Weaver's equivalent discrepancy-theoretic $\mathsf{KS}_2$ formulation, with a universal constant.

0.61

Fast Spectral Signing for Vector Balancing

cs.DS ·2026-09-24 ·Xiaoyu Li
theory similarity 0.64
Abstract

The Komlós conjecture, now a theorem, asserts that whenever the columns of a matrix $A\in\mathbb{R}^{m\times n}$ have Euclidean norm at most one, some signs $\varepsilon\in\{-1,1\}^n$ make every coordinate of $A\varepsilon$ bounded by an absolute constant. Guo, Fang, and Lu gave the first polynomial-time algorithm for finding such signs, a deterministic spectral signing procedure with discrepancy $8272$ and running time $O((mn^9+n^{10})\log(m+n))$. We give a deterministic algorithm that finds signs with $\|A\varepsilon\|_\infty<99$ using $O(mn+n^{ω+2}\log^3 n)$ arithmetic operations, where $ω>2$ is any fixed attainable matrix-multiplication exponent; with the current bounds on $ω$ this is $\widetilde O(mn+n^{4.372})$. Our algorithm uses the same framework: it rounds a single fractional coloring and watches all rows through the top eigenvalue of a Gram matrix of energy-corrected barriers. Steps follow flat directions, rescaled so that no barrier near its threshold moves faster than a constant, and the regularizer grows as coordinates freeze; together these bound the number of updates by $O(n^2\log n)$. A weak quadratic charge on the tracked row sums leaves $O(n\log^2 n)$ rows to evaluate at any time, and a motion clock bounds when any other row could approach its barrier. Each update is a short sequence of matrix products. Its direction is read off by conditional expectations from a polynomial soft projector, its small constraint residual is repaired in affine row representations, and one identity accounts for every change of representation. For rational input the algorithm has polynomial bit complexity.

0.32

The Komlós Problem in Matrix-Multiplication Time

cs.DS cs.DM ·2026-10-14 ·Emile Anand, Peter Chen
similarity 0.64
Abstract · 30 pages

We give a randomized algorithm that, for an $m\times n$ matrix whose columns have Euclidean norm at most one, finds a signing with discrepancy below $99$ in expected $\widetilde O(L_{\mathrm{in}}+n^ω)$ bit operations, where $L_{\mathrm{in}}$ is the input encoding length and $ω$ is the exponent of matrix multiplication. The previous fastest algorithm with a constant discrepancy bound, due to Li, is deterministic and uses $O(mn+n^{ω+2}\log^3 n)$ arithmetic operations. We build on the spectral signing framework of Guo, Fang, and Lu and of Li, which rounds a single fractional coloring while one spectral potential controls every row. Li's potential tracks a top eigenvalue, and the gap below that eigenvalue, which can be of order $1/n$, limits the length of every step. We replace it with a resolvent potential that is smooth without any gap condition, and we draw step signs at random, so that the potential only needs to be concave while progress is measured separately. Our key insight is to reuse a single subspace of directions throughout a batch of steps, thereby using only one spectral computation, so that the more expensive linear algebraic operations are paid for only polylogarithmically often at each scale. Within a batch, we sample directions from a Gaussian completion matrix whose inverse we maintain under rank-one row replacements. Finally, we use a finite-precision analysis to prove stability of the algorithm and attain the bit-complexity bound.

0.39