Is the Algorithmic Kadison-Singer Problem Hard?

Ben Jourdan, Peter Macgregor, He Sun

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We study the following KS₂(c) problem: let c ∈ ℝ^+ be some constant, and v₁,…, v_m ∈ ℝ^d be vectors such that ‖v_i‖² ≤ α for any i ∈ [m] and ∑_{i=1}^m ⟨v_i, x⟩² = 1 for any x ∈ ℝ^d with ‖x‖ = 1. The KS₂(c) problem asks to find some S ⊂ [m], such that it holds for all x ∈ ℝ^d with ‖x‖ = 1 that |∑_{i∈S} ⟨v_i, x⟩² - 1/2| ≤ c⋅√α, or report no if such S doesn't exist. Based on the work of Marcus et al. [Adam Marcus et al., 2013] and Weaver [Nicholas Weaver, 2004], the KS₂(c) problem can be seen as the algorithmic Kadison-Singer problem with parameter c ∈ ℝ^+. Our first result is a randomised algorithm with one-sided error for the KS₂(c) problem such that (1) our algorithm finds a valid set S ⊂ [m] with probability at least 1-2/d, if such S exists, or (2) reports no with probability 1, if no valid sets exist. The algorithm has running time O(binom(m,n)⋅poly(m, d)) for n = O(d/ε² log(d) log(1/(c√α))), where ε is a parameter which controls the error of the algorithm. This presents the first algorithm for the Kadison-Singer problem whose running time is quasi-polynomial in m in a certain regime, although having exponential dependency on d. Moreover, it shows that the algorithmic Kadison-Singer problem is easier to solve in low dimensions. Our second result is on the computational complexity of the KS₂(c) problem. We show that the KS₂(1/(4√2)) problem is FNP-hard for general values of d, and solving the KS₂(1/(4√2)) problem is as hard as solving the NAE-3SAT problem.
Original languageEnglish
Title of host publication34th International Symposium on Algorithms and Computation (ISAAC 2023)
EditorsSatoru Iwata, Naonori Kakimura
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages18
ISBN (Print)978-3-95977-289-1
Publication statusPublished - 28 Nov 2023
Event34th International Symposium on Algorithms and Computation (ISAAC 2023) - Kyoto, Japan
Duration: 3 Dec 20236 Dec 2023
Conference number: 34

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl -- Leibniz-Zentrum für Informatik
ISSN (Electronic)1868-8969


Symposium34th International Symposium on Algorithms and Computation (ISAAC 2023)
Abbreviated titleISAAC 2023
Internet address

Keywords / Materials (for Non-textual outputs)

  • Kadison-Singer problem
  • spectral sparsification


Dive into the research topics of 'Is the Algorithmic Kadison-Singer Problem Hard?'. Together they form a unique fingerprint.

Cite this