Anti-concentration for polynomials of independent random variables

Raghu Meka, Hoi H. Nguyen, Van Vu

Abstract

This paper addresses the fundamental problem of anti-concentration for high-degree polynomials of independent random variables. We establish new, near-optimal "small-ball" probability bounds, demonstrating that such polynomials are unlikely to concentrate their values in small intervals. By employing a regularity lemma and a rank-based decomposition, we bridge the gap between linear and high-degree cases. Our findings provide significant improvements in computational complexity—specifically regarding the correlation of polynomials with the Parity and OR functions—and offer new analytical tools for studying subgraph counts in random graphs.

1. Introduction: The Anti-Concentration Problem

Anti-concentration, or the study of small-ball probabilities, asks a fundamental question: given a function $f$ and random inputs $X_1, \dots, X_n$, what is the maximum probability that $f(X_1, \dots, X_n)$ falls within a specific, narrow range?

This line of inquiry began in 1943 with Littlewood and Offord, who examined linear polynomials (degree $d=1$). They proved that for a sum of $n$ random $\pm 1$ variables with coefficients of magnitude at least 1, the probability of the sum hitting any single value is $O(1/\sqrt{n})$. While the linear case is well-understood, extending these results to higher-degree polynomials (e.g., $d \geq 2$) has proven notoriously difficult. Previous bounds were often weak or decayed too rapidly as the degree increased, leaving a significant gap in our understanding of how high-degree algebraic structures behave under randomness.

2. Methodological Framework

The authors introduce a sophisticated "divide and conquer" strategy to analyze polynomial behavior, centered on three primary pillars:

2.1 The Rank Metric

To quantify the "randomness" inherent in a polynomial, the authors define a "rank" metric. This rank corresponds to the number of disjoint sets of variables that contribute significant coefficients to the polynomial. A high rank suggests that the polynomial's value is determined by many independent components, making it less likely to concentrate.

2.2 Regularity Lemma for Polynomials

A central contribution of this work is a regularity lemma. The authors show that any polynomial can be decomposed into a decision tree structure. At the leaves of this tree, the polynomial exhibits one of two behaviors:

  • Regularity: No single variable exerts disproportionate influence, causing the polynomial to behave similarly to a Gaussian distribution.
  • Tightness: The polynomial is dominated by a constant term and concentrates elsewhere, allowing for iterative simplification.

2.3 Invariance and Iteration

For regular components, the authors apply an invariance principle to compare discrete random variables (such as Rademacher $\pm 1$ flips) to smooth Gaussian variables, where anti-concentration is more mathematically tractable. To further refine the bounds, they utilize an iterative approach to reduce logarithmic factors, moving closer to the conjectured optimal bound of $r^{-1/2}$.

3. Key Insights and Complexity Results

The theoretical advancements in this paper yield immediate applications in computational complexity and graph theory.

3.1 The Parity and OR Functions

In complexity theory, a long-standing challenge posed by Razborov and Viola concerns the correlation of low-degree polynomials with the Parity function. This paper improves the known correlation bounds, showing that polynomials of degree up to approximately $\frac{\log n}{\log \log n}$ cannot significantly correlate with the Parity of $n$ bits. This result narrows the gap toward the conjectured degree limit of $\log n$.

Furthermore, the authors provide the first $\omega(1)$ lower bound for approximating the OR function with polynomials under specific distributions. This demonstrates that low-degree polynomials are fundamentally limited in their ability to mimic the behavior of basic Boolean operators.

3.2 Subgraph Counts in Random Graphs

The paper extends anti-concentration results to the domain of random graphs $G(N, p)$. The authors derive a general result for the number of copies of a fixed subgraph $H$ (such as a triangle). They prove that the distribution of these counts is sufficiently spread out such that the probability of the count equaling any specific integer $m$ is minimized, providing a more granular understanding of the fluctuations in random graph structures.

4. Conclusion and Future Work

This work achieves the conjectured $r^{-1/2}$ anti-concentration rate up to a small sub-polynomial error term. While this represents a major leap forward, a small gap remains—specifically an $\exp(d^2 (\log \log r)^2)$ term in the bound. Future research may focus on eliminating this factor to reach the perfect $r^{-1/2}$ bound and tackling the full Razborov-Viola challenge for polynomials of degree $\log n$. Additionally, characterizing the specific "extremal" polynomials that achieve maximum concentration remains an open and fertile area for investigation.

Summary updated

Abstract

Probabilistic polynomials over commutative rings offer a powerful way of representing Boolean functions. Although many degree lower bounds for such representations have been proved, sparsity lower bounds (counting the number of monomials in the polynomials) have not been so common. Sparsity upper bounds are of great interest for potential algorithmic applications, since sparse probabilistic polynomials are the key technical tool behind the best known algorithms for many core problems, including dense All-Pairs Shortest Paths, and the existence of sparser polynomials would lead to breakthrough algorithms for these problems. In this paper, we prove several strong lower bounds on the sparsity of probabilistic and approximate polynomials computing Boolean functions when 0 means "false". Our main result is that the AND of n ORs of c log n variables requires probabilistic polynomials (over any commutative ring which isn't too large) of sparsity n^Ω(log c) to achieve even 1/4 error. The lower bound is tight, and it rules out a large class of polynomial-method approaches for refuting the APSP and SETH conjectures via matrix multiplication. Our other results include: - Every probabilistic polynomial (over a commutative ring) for the disjointness function on two n-bit vectors requires exponential sparsity in order to achieve exponentially low error. - A generic lower bound that any function requiring probabilistic polynomials of degree d must require probabilistic polynomials of sparsity Ω(2^d). - Building on earlier work, we consider the probabilistic rank of Boolean functions which generalizes the notion of sparsity for probabilistic polynomials, and prove separations of probabilistic rank and probabilistic sparsity. Some of our results and lemmas are basis independent. For example, over any basis {a,b} for true and false where a ≠ b, and any commutative ring R, the AND function on n variables has no probabilistic R-polynomial with 2^o(n) sparsity, o(n) degree, and 1/2^o(n) error simultaneously. This AND lower bound is our main technical lemma used in the above lower bounds.
BibTeX
@inproceedings{meka2016anti,
  author = {Raghu Meka and Hoi H. Nguyen and Van Vu},
  title = {{Anti-concentration for polynomials of independent random variables}},
  booktitle = {Theory Comput},
  year = {2016},
  url = {https://openreview.net/forum?id=Z3bDjJWhGVA},
}

Loading related content...

Figure