License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.108
URN: urn:nbn:de:0030-drops-181606
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18160/
Zhang, Ruizhe ;
Zhang, Xinzhi
A Hyperbolic Extension of Kadison-Singer Type Results
Abstract
In 2013, Marcus, Spielman, and Srivastava resolved the famous Kadison-Singer conjecture. It states that for n independent random vectors v_1,⋯, v_n that have expected squared norm bounded by ε and are in the isotropic position in expectation, there is a positive probability that the determinant polynomial det(xI - ∑_{i=1}^n v_i v_i^⊤) has roots bounded by (1 + √ε)². An interpretation of the Kadison-Singer theorem is that we can always find a partition of the vectors v_1,⋯,v_n into two sets with a low discrepancy in terms of the spectral norm (in other words, rely on the determinant polynomial).
In this paper, we provide two results for a broader class of polynomials, the hyperbolic polynomials. Furthermore, our results are in two generalized settings:
- The first one shows that the Kadison-Singer result requires a weaker assumption that the vectors have a bounded sum of hyperbolic norms.
- The second one relaxes the Kadison-Singer result’s distribution assumption to the Strongly Rayleigh distribution. To the best of our knowledge, the previous results only support determinant polynomials [Anari and Oveis Gharan'14, Kyng, Luh and Song'20]. It is unclear whether they can be generalized to a broader class of polynomials. In addition, we also provide a sub-exponential time algorithm for constructing our results.
BibTeX - Entry
@InProceedings{zhang_et_al:LIPIcs.ICALP.2023.108,
author = {Zhang, Ruizhe and Zhang, Xinzhi},
title = {{A Hyperbolic Extension of Kadison-Singer Type Results}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {108:1--108:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18160},
URN = {urn:nbn:de:0030-drops-181606},
doi = {10.4230/LIPIcs.ICALP.2023.108},
annote = {Keywords: Kadison-Singer conjecture, Hyperbolic polynomials, Strongly-Rayleigh distributions, Interlacing polynomials}
}
|
Keywords: |
|
Kadison-Singer conjecture, Hyperbolic polynomials, Strongly-Rayleigh distributions, Interlacing polynomials |
|
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.07.2023 |
