Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-208 | 24th September 2026 00:33

Exponential Correlation Bounds for Polynomials

RSS-Feed




TR26-208
Authors: Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee, Shachar Lovett, Avishay Tal, Emanuele Viola
Publication: 24th September 2026 01:29
Downloads: 155
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint