ECCC-Report TR19-145https://eccc.weizmann.ac.il/report/2019/145Comments and Revisions published for TR19-145en-usThu, 31 Oct 2019 08:42:35 +0200
Paper TR19-145
| XOR Lemmas for Resilient Functions Against Polynomials |
Eshan Chattopadhyay,
Pooya Hatami,
Kaave Hosseini,
Shachar Lovett,
David Zuckerman
https://eccc.weizmann.ac.il/report/2019/145A major challenge in complexity theory is to explicitly construct functions that have small correlation with low-degree polynomials over $F_2$. We introduce a new technique to prove such correlation bounds with $F_2$ polynomials. Using this technique, we bound the correlation of an XOR of Majorities with constant degree polynomials. In fact, we prove a more general XOR lemma that extends to arbitrary resilient functions. We conjecture that the technique generalizes to higher degree polynomials as well.
A key ingredient in our new approach is a structural result about the Fourier spectrum of low degree polynomials over $F_2$. We show that for any n-variate polynomial $p$ over $F_2$ of degree at most $d$, there is a small set $S \subset [n]$ of variables, such that almost all of the Fourier mass of $p$ lies on Fourier coefficients that intersect with $S$. In fact our result is more general, and finds such a set $S$ for any low-dimensional subspace of polynomials. This generality is crucial in deriving the new XOR lemmas.Thu, 31 Oct 2019 08:42:35 +0200https://eccc.weizmann.ac.il/report/2019/145