Projects per year

## 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 |
---|---|

Title of host publication | 34th International Symposium on Algorithms and Computation (ISAAC 2023) |

Editors | Satoru Iwata, Naonori Kakimura |

Place of Publication | Dagstuhl, Germany |

Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |

Pages | 1-18 |

Number of pages | 18 |

Volume | 283 |

ISBN (Print) | 978-3-95977-289-1 |

DOIs | |

Publication status | Published - 28 Nov 2023 |

Event | 34th International Symposium on Algorithms and Computation (ISAAC 2023) - Kyoto, Japan Duration: 3 Dec 2023 → 6 Dec 2023 Conference number: 34 https://www.kurims.kyoto-u.ac.jp/isaac/isaac2023/ |

### Publication series

Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|

Publisher | Schloss Dagstuhl -- Leibniz-Zentrum für Informatik |

ISSN (Electronic) | 1868-8969 |

### Symposium

Symposium | 34th International Symposium on Algorithms and Computation (ISAAC 2023) |
---|---|

Abbreviated title | ISAAC 2023 |

Country/Territory | Japan |

City | Kyoto |

Period | 3/12/23 → 6/12/23 |

Internet address |

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

- Kadison-Singer problem
- spectral sparsification

## Fingerprint

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

- 1 Active