Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR18-155 | 8th September 2018 15:35

#### Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates

TR18-155
Authors: Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal
Publication: 8th September 2018 15:40
As an application, we give a concrete conjecture for bounds on the second level of the Fourier tails for low degree polynomials over the finite field $\mathbb{F}_2$. If true, it would imply an efficient pseudorandom generator for $\text{AC}^0[\oplus]$, a well-known open problem in complexity theory. As a stepping stone towards resolving this conjecture, we prove such bounds for the first level of the Fourier tails.