Name
Abstract | ||
|---|---|---|
A major challenge in complexity theory is to explicitly construct functions that have small correlation with low-degree polynomials over F2. We introduce a new technique to prove such correlation bounds with F2 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 F2. We show that for any n-variate polynomial p over F2 of degree at most d, there is a small set S ⊂ [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.
|
Year | DOI | Venue |
|---|---|---|
2020 | 10.1145/3357713.3384242 | STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing
Chicago
IL
USA
June, 2020 |
Keywords | DocType | ISSN |
Pseudorandom Generators, Low-degree polynomials, Correlation bounds, Resilient functions | Conference | 0737-8017 |
ISBN | Citations | PageRank |
978-1-4503-6979-4 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eshan Chattopadhyay | 1 | 84 | 11.71 |
| Pooya Hatami | 2 | 94 | 14.40 |
| Kaave Hosseini | 3 | 0 | 0.68 |
| Shachar Lovett | 4 | 520 | 55.02 |
| David Zucherman | 5 | 2588 | 266.65 |