Kadison--Singer in Deterministic Polynomial Time
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Kadison--Singer in Deterministic Polynomial Time".
Jane: Here's the gist of the paper. We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices H1,..., HN of rank at most one, finds signs s ∈ ±1 N with∥ P i siHi∥ ≤ 13∥ P i H2 i∥ 1/2 <ref:2609.17266#pg6>.
Tom: As a corollary, for vectors vi with P i viv∗i = I and∥vi∥2 ≤ δ, the signs yield a partition
N: = S1∪S2 such that each part satisfies∥ P i∈Sj viv∗i − I 2∥ ≤ 13 2√δ for j = 1, 2 <ref:2609.17266#pg7>.
Jane: This gives a deterministic polynomial-time algorithm for the Kadison–Singer problem, in Weaver’s equivalent discrepancytheoretic KS2 formulation, with a universal constant <ref:2609.17266#pg9>.
Tom: Problem Formulation and Algorithmic Context The Kadison–Singer problem
KS59: , in the equivalent discrepancy-theoretic KS2 formulation of Weaver
Wea04: , asks for a partition of
N: into two parts S1 ∪ S2 such that each one of the parts P i∈Sj viv∗i is close to 1/2I within an error that depends only on δ for j = 1, 2 <ref:2609.17266#pg10>.
Paper summary: Tom: So we've covered the deterministic polynomial time algorithm for Kadison--Singer in this paper called "Kadison--Singer in Deterministic Polynomial Time". It gives us a way to find signs for rank-one matrices.
Jane: To put it simply, the authors proved that if you have certain vectors and matrices that satisfy some conditions, you can find a partition into two sets where each set behaves nicely with respect to those vectors.
Lu: The implication is that this moves the Kadison--Singer problem from just a theoretical existence question to an algorithmic one, providing a deterministic path to finding the partition.
Meng: For someone trying to deploy models or run large simulations, having a deterministic polynomial time algorithm is crucial because it means we can actually compute the solution reliably on hardware without relying on random chance.
Tom: The authors use this potential function method with their key lemmas to guarantee that this process terminates in polynomial time and gives us a concrete bound on how close each partition gets to being ideal.
Jane: It's important to remember that they are working within the discrepancy-theoretic formulation of the Kadison-Singer problem, which is Weaver's KS2 formulation, not just the original one.
Lu: The paper connects this result back to bounds on rank one matrix discrepancy, which shows it sits within a larger area of research concerning how we can control these types of matrix structures.
Meng: What this means for us in practice is that if we are dealing with problems where we need to partition data or resources based on these matrices, and the underlying structure is rank one, then this gives us a deterministic method instead of just hoping a random approach works well enough.
Tom: It's about taking a problem that was previously known to be hard for an efficient algorithm and showing it can be solved deterministically in polynomial time with this specific framework.
Conclusion: Tom: So, we've been looking at this paper from arXiv titled "Kadison--Singer in Deterministic Polynomial Time" by Anari, Gharan, Saberi, and Srivastava.
Jane: To put it simply, they’re taking a really hard problem about partitioning matrices and showing you can find a way to do it deterministically using polynomial time.
Lu: It tackles the Kadison-Singer problem in its discrepancy theory version. That's essentially about finding two groups of matrices where each group has vectors that are pretty close to being perfectly balanced with respect to those matrices.
Meng: So, what does this actually mean for a system? If you have a large set of data points represented by these matrices, this suggests we can find a reliable way to split them into two manageable groups without relying on luck or guessing.
Tom: It’s about turning something that was theoretical into something you can actually run on hardware fast. The authors use a potential function method, which is essentially a clever mathematical trick to guide the search towards the correct answer deterministically.
Jane: The core idea is that they showed how to find signs, those plus and minus ones we talked about before, in polynomial time for these rank one matrices. That’s the main result they are highlighting here.
Lu: They establish a universal constant for this bound, which means no matter how complex the structure of these matrices is—as long as they are rank one—the error in the final partition stays within a certain limit that depends only on some initial setup parameter.
Meng: I’m still wondering about what kind of matrices they actually used to test this. It sounds like it’s a theoretical guarantee, but I need to know if this applies to the messy, real-world data we deal with every day.
Tom: That's exactly the next thing we look at. We need to see how these theoretical guarantees translate when we put them into a system that actually has input data instead of perfect mathematical examples.
University of Chicago
cs.DS, cs.DM, math.CO, math.FA
Submitted: 2026-09-15
Updated: 2026-11-03
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 89/100
The gist: We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices H1,..., HN of rank at most one, finds signs s ∈ ±1 N with∥ P i siHi∥ ≤ 13∥ P i H2 i∥ 1/2 <ref:2609.17266#pg6>.
Key concepts
- Kadison–Singer Problem (KS2)
- This is a problem in operator theory asking for a partition of indices into two sets, S1 and S2, such that the vectors corresponding to those sets have inner products close to 1/2. The goal is to find this partition efficiently.
- Discrepancy Theory
- This framework uses discrepancy theory to measure how far a set of vectors is from being perfectly balanced. In this context, it quantifies the difference between the actual inner product of a subset and the ideal value (like 1/2) using specific error bounds.
- Potential Function ($\Psi(x)$)
- The algorithm uses a potential function to guide its steps. This function combines an optimal SDP value with terms involving matrix variables. The key idea is that at every step, a deterministic move can be made that does not increase this potential, ensuring the process eventually terminates.
- Rank-One Hermitian Matrices
- The input matrices are specific types of matrices called rank-one Hermitian matrices. These are important because they simplify the analysis, allowing researchers to find bounds and algorithms for problems involving these particular structures.
Terminology
Summary
We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices H1,. p. 0.., HN of rank at most one, finds signs s ∈ ±1 N with∥ P i siHi∥ ≤ 13∥ P i H2 i∥ 1/2 <ref:2609. p. 017266#pg6>. As a corollary, for vectors vi with P i viv∗i = I and∥vi∥2 ≤ δ, the signs yield a partition [N] = S1∪S2 such that each part satisfies∥ P i∈Sj viv∗i − I 2∥ ≤ 13 2√δ for j = 1, 2 <ref:2609. p. 017266#pg7>. This gives a deterministic polynomial-time algorithm for the Kadison–Singer problem, in Weaver’s equivalent discrepancytheoretic KS2 formulation, with a universal constant <ref:2609. p. 017266#pg9>.
Problem Formulation and Algorithmic Context
The Kadison–Singer problem [KS59], in the equivalent discrepancy-theoretic KS2 formulation of Weaver [Wea04], asks for a partition of [N] into two parts S1 ∪ S2 such that each one of the parts P i∈Sj viv∗i is close to 1/2I within an error that depends only on δ for j = 1, 2 <ref:2609.17266#pg10>. In breakthrough work, Marcus, Spielman, and Srivastava [MSS15] proved that a partition with∥ P i∈Sj viv∗i∥ ≤ 1/2(1 + √2δ)2 for both parts always exists. p. 1 Jourdan, Macgregor, and Sun [JMS22] formulated the algorithmic version as the problem KS2(c), which asks for a polynomial time algorithm to find a partition with∥ P i∈Sj viv∗i − I/2∥ ≤ c√δ for constant c. p. 1
Algorithm Structure and Potential Function
The algorithm is based on a potential function Ψ(x) = R(x) + λP i ψi(x), where R(x) is the optimal value of a semidefinite program defined by constraints involving S(x) and coordinate budgets. The terms in the matrix part act as reservoirs, and the potential function is designed such that at each step, a deterministic move can be found that does not increase Ψ(x), ensuring the final discrepancy is bounded by the initial potential. p. 2
Key Analytical Tools
The proof relies on two key lemmas. Lemma 3.1 shows how the matrix potential controls the spectrum of S(x), providing a bound that relates R(x) to∥S(x)∥ and the error terms. p. 4 Lemma 3.2 supplies progress at every nonterminal state x, guaranteeing either an endpoint move or a random step with drift and covariance that decreases the potential. p. 4
Movement Strategy and Termination
The algorithm employs three types of movements at each iteration: (1) Endpoint movement, (2) Hessian descent movement, and (3) Gradient coordinate movement. The potential decrease is guaranteed by showing that one of these movements decreases Ψ by at least 1/poly(N), leading to termination in at most poly(N) iterations. p. 6
Quantitative Bounds and Complexity
The analysis establishes a final bound on the discrepancy, showing that the algorithm reaches a vertex x f ∈ ±1 N which satisfies∥ X i(x f i − x 0 i)Ai∥ ≤ R(x f) = Ψ(x f) ≤ Ψ(x 0) ≤ 2√42 + 1/100√ν ≤ 13√ν. The algorithm is implemented in polynomial time using semidefinite programming and eigenvalue computation. p. 6
Proof of Key Lemmas
Lemma 4.3 proves that for every active coordinate i and every direction h ∈ R n, ∂iR = αipi − βiqi, h⊤∇2Rh ≤ O(Eh) − Ω(c)X i∈[n] (−ψ''i)h 2i (bipi + aiqi). Lemma 4.5 provides a covariance guarantee that ensures the energy bound is controlled by E∥H∥ squared, leading to ωi = e⊤ i [I, −B]Γ[I, −B]⊤ei ≤ κe⊤ i (I + B 2)ei ≤ κ(1 +∥B∥ 2) = O((1 + N) 2).
AI Usage and Conclusion
The idea for the proof in this article was found by Anthropic’s Claude Fable 5.1 model, working from material supplied by the authors. The main ideas are connected to notions in free probability and movements used to decrease the potential, endpoint movement and random local steps had already been considered in earlier attempts on KS2. The authors remain fully responsible for the content of the article. p. 1
References
[AOSS18] Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Nikhil Srivastava. Approximating the largest root and applications to interlacing families. p. 1
[AS26] Emrullah Akbas and Suvrit Sra. p. 1 A proof of the matrix spencer conjecture. p. 1
[Ban24] Nikhil Bansal. p. 2 On a generalization of iterated and randomized rounding. p. 4
[BJ25] Nikhil Bansal and Haotian Jiang. p. 0 An improved bound for the Beck-Fiala conjecture. p. 1
[BLV22] Nikhil Bansal, Aditi Laddha, and Santosh Vempala. p. 1 A unified approach to discrepancy minimization. p. 0
[BV04] Stephen P Boyd and Lieven Vandenberghe. p. 7 Convex optimization. p. 4
[JMS22] Ben Jourdan, Peter Macgregor, and He Sun. p. 1 Is the algorithmic kadison-singer problem hard? p. 0
[KLS20] Rasmus Kyng, Kyle Luh, and Zhao Song. p. 1 Four deviations suffice for rank 1 matrices. p. 0
[KS59] Richard V. p. 1 Kadison and Isadore M. p. 0 Singer. Extensions of pure states.
[Leh99] Franz Lehner. Computing norms of free operators with matrix coefficients. p. 0
[MSS15] Adam W Marcus, Daniel A Spielman, and Nikhil Srivastava. p. 1 Interlacing families II: Mixed characteristic polynomials and the Kadison–Singer problem. p. 1
[MSS22] Adam W Marcus, Daniel A Spielman, and Nikhil Srivastava. p. 1 Finite free convolutions of polynomials. p. 1
[PV23] Lucas Pesenti and Adrian Vladu. p. 1 Discrepancy minimization via regularization. p. 1
[PvH25] Emre Parmaksiz and Ramon van Handel. Computing extreme singular values of free operators. p. 9
[Wea04] Nik Weaver. p. 1 The Kadison–Singer problem in discrepancy theory. p. 1
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Deterministic polynomial-time solution for rank one matrix discrepancy: The improved AI system can find signs s in two parts S1 and S2 such that each part satisfies P i in S j v i v i star = 1/2 I within an error of 13/2 sqrt(delta).
-
Algorithmic resolution of the Kadison-Singer problem: The system can solve KS2(c) in polynomial time with a universal constant, meaning it can find a partition [N] = S1 U S2 such that each part satisfies P i in S j v i v i star - I/2 <= 13/2 sqrt(delta).
-
Efficient potential-based optimization: The system utilizes a potential function Psi(x) = R(x) + lambda Phi(x) to guide decisions, allowing it to find a deterministic move at each step that does not increase the potential, leading to termination in at most poly(N) iterations.
Sources
- An Improved Bound for the Beck-Fiala Conjecture
- Is the Algorithmic Kadison-Singer Problem Hard?
- Computing extreme singular values of free operators
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time