Anti-concentration for polynomials of Rademacher random variables and applications in complexity theory
Anti-concentration for polynomials of Rademacher random variables and applications in complexity theory
复制标题
Rademacher随机变量多项式的反集中及其在复杂性理论中的应用
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
V. Vu
中科院分区：
文献类型：
--
作者：
Raghu Meka;Oanh Nguyen;V. Vu
我们证明了具有任意程度的独立随机变量多项式的抗浓缩结果。我们的结果扩展了线性多项式的经典Littlewood-offord结果，并改善了一些早期的估计。我们讨论了两个不同领域的应用。在复杂性理论中，我们证明了计算奇偶校验的最佳下限，解决了Razborov和Viola提出的复杂性理论中的挑战，并且还解决了有关或功能的问题。在随机图理论中，我们在随机图中的固定图的副本数量上得出了一般的抗浓缩结果。
We prove anti-concentration results for polynomials of independent random variables with arbitrary degree. Our results extend the classical Littlewood-Offord result for linear polynomials, and improve several earlier estimates. We discuss applications in two different areas. In complexity theory, we prove near optimal lower bounds for computing the Parity, addressing a challenge in complexity theory posed by Razborov and Viola, and also address a problem concerning OR functions. In random graph theory, we derive a general anti-concentration result on the number of copies of a fixed graph in a random graph.