Is the Algorithmic Kadison-Singer Problem Hard?

05/04/2022

∙

by   Ben Jourdan, et al.

∙

0

∙

share

We study the following 𝖪𝖲_2(c) problem: let c ∈ℝ^+ be some constant, and v_1,…, v_m∈ℝ^d be vectors such that v_i^2≤α for any i∈[m] and ∑_i=1^m ⟨ v_i, x⟩^2 =1 for any x∈ℝ^d with x=1. The 𝖪𝖲_2(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⟩^2 - 1/2| ≤ c·√(α), or report no if such S doesn't exist. Based on the work of Marcus et al. and Weaver, the 𝖪𝖲_2(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 𝖪𝖲_2(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(mn·poly(m, d))  n = O(d/ϵ^2log(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, 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 𝖪𝖲_2(c) problem. We show that the 𝖪𝖲_2(1/(4√(2))) problem is 𝖥𝖭𝖯-hard for general values of d, and solving the 𝖪𝖲_2(1/(4√(2))) problem is as hard as solving the 𝖭𝖠𝖤3𝖲𝖠𝖳 problem.