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 and vectors satisfying
find, in polynomial time, a partition and a universal constant such that
Here is the conjugate transpose, 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 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 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 . Since the two partial frame operators sum to , this also yields a two-sided approximation to . 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
Progress summary
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.