Is the algorithmic Kadison-Singer problem hard?

DOI10.4230/LIPICS.ISAAC.2023.43MaRDI QIDQ6953174zbMATH OpenFDO

Authors Ben Jourdan, Peter Macgregor, He Sun

Publication date 24 July 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2023.43

zbMATH Keywords

Kadison-Singer problemspectral sparsification

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• Approximating the largest root and applications to interlacing families
• Approximating vector scheduling: almost matching upper and lower bounds
• Constructive algorithms for discrepancy minimization
• Extensions of Pure States
• Finding a bounded-degree expander inside a dense one
• Graph sparsification by effective resistances
• Hardness results for Weaver's discrepancy problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• On Multidimensional Packing Problems
• Online row sampling
• The Kadison--Singer problem in mathematics and engineering: a detailed account
• The Kadison-Singer problem in discrepancy theory.
• Tight hardness results for minimizing discrepancy
• Twice-Ramanujan sparsifiers
• User-friendly tail bounds for sums of random matrices

Cited in

(1)

• Weaver's discrepancy for Gaussian random vectors

This page was built for publication: Is the algorithmic Kadison-Singer problem hard?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6953174)