# 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 language English 34th International Symposium on Algorithms and Computation (ISAAC 2023) Satoru Iwata, Naonori Kakimura Dagstuhl, Germany Schloss Dagstuhl - Leibniz-Zentrum für Informatik 1-18 18 283 978-3-95977-289-1 https://doi.org/10.4230/LIPIcs.ISAAC.2023.43 Published - 28 Nov 2023 34th International Symposium on Algorithms and Computation (ISAAC 2023) - Kyoto, JapanDuration: 3 Dec 2023 → 6 Dec 2023Conference number: 34https://www.kurims.kyoto-u.ac.jp/isaac/isaac2023/

### Publication series

Name Leibniz International Proceedings in Informatics (LIPIcs) Schloss Dagstuhl -- Leibniz-Zentrum für Informatik 1868-8969

### Symposium

Symposium 34th International Symposium on Algorithms and Computation (ISAAC 2023) ISAAC 2023 Japan Kyoto 3/12/23 → 6/12/23 https://www.kurims.kyoto-u.ac.jp/isaac/isaac2023/

## Keywords / Materials (for Non-textual outputs)

• spectral sparsification

## Fingerprint

Dive into the research topics of 'Is the Algorithmic Kadison-Singer Problem Hard?'. Together they form a unique fingerprint.
• ### Efficient Spectral Algorithms for Massive and Dynamic Graphs

Sun, H.

EPSRC

1/01/2031/12/24

Project: Research