Search Results

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.