Anti-concentration for Polynomials of Independent Random Variables

Anti-concentration for Polynomials of Independent Random Variables
复制标题

独立随机变量多项式的反集中

DOI：
10.4086/toc.2016.v012a011
复制
发表时间：
2015
期刊：
Theory Comput.
影响因子：
--
通讯作者：
V. Vu
V. Vu
中科院分区：
--
文献类型：
--
作者：
Raghu Meka;Oanh Nguyen;V. Vu

文献摘要

被引文献

相似文献

证明了任意次数独立随机变量多项式的反集中结果。我们的结果推广了经典的线性多项式的Littlewood-Offord结果，改进了几个较早的估计。 我们讨论两个不同领域的应用。在复杂性理论中，我们证明了计算奇偶校验的最优下界，解决了Razborov和Viola在复杂性理论中提出的挑战，并解决了有关OR函数的问题。在随机图论中，我们得到了一个关于随机图中固定图的拷贝数的一般反集中结果。
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.