← All problems

10 Lectures and 42 Open Problems — Constructive Kadison-Singer

“Give a (polynomial time) construction of the tight frame partition satisfying the properties required in the Kadison-Singer problem (or the related Weaver’s conjecture). These partitions were proven to exist (with a non-constructive proof) in the recent breakthrough of Marcus, Spielman, and Srivastava.” Polynomial Time Algorithms for the Kadison-Singer Problem Rank-One Matrix Discrepancy and Algorithmic Kadison–Singer

A standard precise formulation of the associated algorithmic Weaver problem is this: given positive integers m,dm,d and vectors a1,…,am∈Cda_1,\ldots,a_m\in\mathbb{C}^d satisfying

∑i=1maiai∗=Id,∥ai∥2≤α(i∈[m]),\sum_{i=1}^m a_i a_i^*=I_d, \qquad \|a_i\|^2\leq\alpha\quad(i\in[m]),

find, in polynomial time, a partition [m]=I1⊔I2[m]=I_1\sqcup I_2 and a universal constant CC such that

∥∑i∈Ijaiai∗−Id2∥≤Cα(j=1,2).\left\|\sum_{i\in I_j}a_i a_i^*-\frac{I_d}{2}\right\|\leq C\sqrt{\alpha}\quad(j=1,2).

Here ai∗a_i^* is the conjugate transpose, IdI_d is the identity, and the norm is the operator norm. The universal constant is independent of the input dimensions and vectors. The original direction does not state a particular value of CC or specify an input model for “polynomial time.” Polynomial Time Algorithms for the Kadison-Singer Problem Rank-One Matrix Discrepancy and Algorithmic Kadison–Singer

Background

The Kadison–Singer problem originated in operator theory; Weaver’s finite-dimensional KS2\mathsf{KS}_2 formulation connects it to partitioning an isotropic vector family, meaning one whose rank-one outer products sum to the identity. In that formulation, the aim is to split the frame so that both partial frame operators are close to half the identity, with error governed by the largest squared vector norm rather than the ambient dimension. This turns an operator-theoretic existence question into a matrix-discrepancy problem: one choice of signs must control all directions simultaneously. Ezeunala and Jiang (2026) Polynomial Time Algorithms for the Kadison-Singer Problem

Marcus, Spielman, and Srivastava resolved the existence question in 2015 using interlacing families and mixed characteristic polynomials. In the normalization above, their theorem gives a partition for which each part has operator norm at most (1/2+α)2(1/\sqrt{2}+\sqrt{\alpha})^2. Since the two partial frame operators sum to IdI_d, this also yields a two-sided approximation to Id/2I_d/2. The proof’s polynomial-root selection establishes existence, but does not itself give an efficient construction of the partition. Marcus, Spielman, and Srivastava (2015) Polynomial Time Algorithms for the Kadison-Singer Problem

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.