Source-linked AI summary
Exponential Correlation Bounds for Polynomials
Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee, Shachar Lovett, Avishay Tal, Emanuele Viola
TL;DR
Proving correlation bounds for low-degree polynomials is a longstanding challenge with connections to other complexity problems. The paper extends Smolensky’s encoding argument to tuples and establishes exponential correlation bounds for XORs of disjoint-block majorities. Its results also support polylogarithmic-seed pseudorandom generators for low-degree polynomials and alternating circuits with parity gates.
Problem
Correlation bounds for low-degree polynomials are a longstanding challenge and a prerequisite for progress on problems including matrix rigidity, multiparty communication complexity, circuit lower bounds, and pseudorandomness.
Source: §1 · pp. 1–2Method
The proof extends Smolensky’s encoding argument to tuples, introduces weights for functions and a multiplication lemma, and proves the main theorem by dimension counting.
Source: §2 · p. 2Results
The paper establishes exponential correlation bounds for XORs of disjoint-block majorities and reports that its bound is tight up to a constant.
Source: §1 · p. 2Takeaways & Limitations
The hard function supports pseudorandom generators with polylogarithmic seed length for low-degree polynomials over F2 and polynomial-size alternating circuits with parity gates.
Source: §1 · p. 2The stated theorem setup concerns multilinear polynomials in kℓ variables of total degree at most d.
Source: §2.3 · p. 5
Abstract
from arXiv · showhide
We prove that the XOR of $k$ majorities on disjoint blocks of \(\ell\) bits has correlation at most \((2d/\sqrt{\ell})^k\) with every degree-\(d\) polynomial over \(\mathbb F_2\). By known techniques, this implies pseudorandom generators with polylogarithmic seed length for low-degree polynomials over $\mathbb F_2$ and for alternating circuits with parity gates.
1 Introduction
The introduction presents exponential correlation bounds for XORs of majorities on disjoint blocks, addressing a longstanding challenge in low-degree polynomial analysis. It also describes pseudorandom-generator applications for low-degree polynomials and alternating circuits with parity gates.
1 Introduction
- Correlation bounds for low-degree polynomials are presented as a prerequisite for progress on challenges including matrix rigidity, multiparty communication complexity, circuit lower bounds, and pseudorandomness.For degree-d polynomials over F2, earlier work proved correlation below cd/√n with Majority, a bound described as tight; for d ≥ log n, no explicit function was known to have asymptotically smaller correlation.Source: §1 · pp. 1–2
- The paper obtains exponential correlation bounds for the XOR of majorities on disjoint blocks, including for polynomials whose degree is a power of the input length.The introduction identifies this function as a natural candidate considered in prior work.Source: §1 · p. 2
- The stated correlation bound is tight up to a constant, by applying the construction in to each block.Source: §1 · p. 2
- The Nisan–Wigderson construction based on the hard function yields pseudorandom generators with polylogarithmic seed length for degree-d polynomials over F2.The introduction contrasts this with previous generators whose seed length depended exponentially on the degree, which gave nothing for d ≥ log n.Source: §1 · p. 2
- Combining Razborov’s polynomial approximation with the Nisan–Wigderson construction gives polylogarithmic-seed generators for polynomial-size alternating circuits with parity gates.The introduction reports a previous best seed length of n(1 −o(1)).Source: §1 · p. 2
2 Proof of Main Result
The proof extends Smolensky’s encoding argument to tuples, using blockwise interpolation, a weight that controls multiplication, and dimension counting.
2 Proof of Main Result
- The proof’s overall strategy extends Smolensky’s encoding argument to tuples and combines preliminaries, a new weight, a multiplication lemma, and dimension counting.The proof is organized around these ingredients.Source: §2 · p. 2
2.1 Preliminaries and Notation
- For each majority-pattern region Hα, a unique polynomial fα in W agrees with f there, enabling blockwise interpolation over all k blocks.W consists of multilinear polynomials with degree at most m in each block.Source: §2.1 · p. 3
2.2 Weight
- The weight is the largest basis-term weight in a function’s h-basis expansion, and multiplication by a degree-t polynomial raises it by at most t.Blocks represented by h-factors contribute m+1; other blocks contribute their monomial degree.Source: §2.2 · p. 4
2.3 Proof of the Main Theorem by Dimension Counting
- Dimension counting bounds the disagreement set by representing every function on it using a space of restricted dimension.The proof constructs a span of selected h-basis functions and shows its restriction to the set is surjective.Source: §2.3 · pp. 5, 7
- For each non-exceptional monomial, the proof omits products containing a chosen low-degree block’s h-factor; exceptional monomials retain all such products.Exceptional indices have block degree greater than m-d in every block.Source: §2.3 · p. 5
A PRG from Nisan-Wigderson Construction
This section constructs an explicit PRG for degree-d polynomials by applying the Nisan–Wigderson construction separately to each majority block and analyzing output-replacement hybrids. The blockwise XOR structure keeps restricted output degrees small and saves a factor of k over applying the construction to the whole hard function.
A PRG from Nisan-Wigderson Construction
- Theorem A.1 gives an explicit PRG that ε-fools degree-d polynomials over F2 on n variables.The supplied theorem passage does not include its seed-length expression.Source: A PRG from Nisan-Wigderson Construction · p. 9
- The construction uses k independent seeds and chooses odd ℓ = Θ(d^2t^2), with k = ⌈log(2n/ε)⌉.The NW sets have size ℓ, pairwise intersections below t, and universe size R = O(ℓ^2/t).Source: A PRG from Nisan-Wigderson Construction · p. 9
- In the hybrid analysis, each earlier output is an XOR of block-local functions of fewer than t variables, so its degree is at most t and each substituted polynomial has degree at most dt.Applying NW separately to the majority blocks preserves this degree bound despite the XOR across blocks.Source: A PRG from Nisan-Wigderson Construction · pp. 9–10
A PRG from Nisan-Wigdner Construction
- Theorem 1.1 bounds each conditional acceptance-probability difference, and averaging over fixed bits and summing the n hybrids proves Theorem A.1.The hybrids replace the generator outputs one at a time.Source: A PRG from Nisan-Wigderson Construction · pp. 9–10
- Using the XOR structure saves a factor of k = Θ(log(n/ε)) in seed length compared with applying NW directly to the entire hard function.The comparison is with a direct construction using sets over all kℓ input bits.Source: A PRG from Nisan-Wigderson Construction · p. 10
B Fourier Bounds for Polynomials and an alternate PRG
The paper derives Fourier bounds for degree-d polynomials from their correlation with XORs of block majorities, and uses those bounds to obtain an alternative polynomial PRG. It also combines polynomial-fooling PRGs with Razborov’s approximation to obtain PRGs for AC0[⊕] circuits.
B Fourier Bounds for Polynomials and an alternate PRG
- Our correlation bound resolves a conjectured Fourier bound for polynomials [CGL+21, Conjecture 31] and, using a result from [CGL+21] based on the frameworks of polarizing random walks, yields an alternative pseudorandom generator for polynomials.Source: B Fourier Bounds for Polynomials and… · p. 10
- As ℓ grows, the Fourier expansion leaves only sets containing one variable from each part, because terms missing a part vanish and terms with multiple variables in a part tend to zero.For fixed odd |T| > 1, the normalized majority Fourier coefficient tends to zero.Source: B Fourier Bounds for Polynomials and… · p. 11
- Corollary B.2 gives an explicit PRG that ε-fools degree-d polynomials over F2 on n variables.The supplied corollary passage omits its seed-length expression.Source: B Fourier Bounds for Polynomials and… · p. 12
- Theorem C.1 states explicit PRG seed-length bounds for size-s, depth-∆ AC0[⊕] circuits using both the NW and Fourier-bound constructions.The supplied theorem passages identify the two constructions but omit the seed-length expressions.Source: B Fourier Bounds for Polynomials and… · p. 12
- Razborov’s polynomial approximation lets both polynomial-fooling PRGs also fool AC0[⊕] circuits.The approximation has degree d = O(log^(∆−1)(s) log(1/ε)) and pointwise error at most ε/3.Source: B Fourier Bounds for Polynomials and… · p. 12