论文标题
双曲线浓度，抗浓度和差异
Hyperbolic Concentration, Anti-concentration, and Discrepancy
论文作者
论文摘要
Chernoff Bound是理论计算机科学的基本工具。它已被广泛用于随机算法设计和随机类型分析。差异理论涉及寻找设定系统的双色，以使每组的着色是平衡的，在近似算法设计中具有大量应用。 Chernoff Bound [Che52]暗示，任何具有$ n $ sets和$ n $元素的设置系统的随机双色将具有差异$ O（\ sqrt {n \ log n}）$具有很高的可能性，而Spencer [spe85]的著名结果[spe85]表明，存在$ o（\ o（\ o（\ sqrt sqrt}）$ ciffere visse） 双曲线多项式的研究可以追溯到20世纪初，当时使用Gårding[Går59]来解决PDES。近年来，在控制理论，优化，实际代数几何形状等中发现了更多应用。特别是，Marcus，Spielman和Srivastava [MSS15]使用双曲线多项式理论来证明Kadison-Serger猜想[KS59]，这与差异理论密切相关。 在本文中，我们介绍了双曲线多项式的新结果列表： *我们显示了两个近乎最佳的双曲线切尔诺夫边界：一个用于任意向量的Rademacher总和，另一个用于双曲线锥中的随机向量。 *我们显示出双曲线抗浓缩结合。 *我们将双曲线kadison-singer定理[Brä18]推广到亚偏性位置的向量，并证明了任何恒定的双曲线级别向量的双曲线Spencer定理。 经典的矩阵Chernoff和差异结果基于决定性多项式。据我们所知，本文是第一份显示双曲多项式浓度或抗浓度结果的作品。我们希望我们的发现为双曲线和差异理论提供更多的见解。
Chernoff bound is a fundamental tool in theoretical computer science. It has been extensively used in randomized algorithm design and stochastic type analysis. Discrepancy theory, which deals with finding a bi-coloring of a set system such that the coloring of each set is balanced, has a huge number of applications in approximation algorithms design. Chernoff bound [Che52] implies that a random bi-coloring of any set system with $n$ sets and $n$ elements will have discrepancy $O(\sqrt{n \log n})$ with high probability, while the famous result by Spencer [Spe85] shows that there exists an $O(\sqrt{n})$ discrepancy solution. The study of hyperbolic polynomials dates back to the early 20th century when used to solve PDEs by Gårding [Går59]. In recent years, more applications are found in control theory, optimization, real algebraic geometry, and so on. In particular, the breakthrough result by Marcus, Spielman, and Srivastava [MSS15] uses the theory of hyperbolic polynomials to prove the Kadison-Singer conjecture [KS59], which is closely related to discrepancy theory. In this paper, we present a list of new results for hyperbolic polynomials: * We show two nearly optimal hyperbolic Chernoff bounds: one for Rademacher sum of arbitrary vectors and another for random vectors in the hyperbolic cone. * We show a hyperbolic anti-concentration bound. * We generalize the hyperbolic Kadison-Singer theorem [Brä18] for vectors in sub-isotropic position, and prove a hyperbolic Spencer theorem for any constant hyperbolic rank vectors. The classical matrix Chernoff and discrepancy results are based on determinant polynomial. To the best of our knowledge, this paper is the first work that shows either concentration or anti-concentration results for hyperbolic polynomials. We hope our findings provide more insights into hyperbolic and discrepancy theories.
