ECCC-Report TR18-155https://eccc.weizmann.ac.il/report/2018/155Comments and Revisions published for TR18-155en-usSat, 08 Sep 2018 15:40:48 +0300
Paper TR18-155
| Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates |
Eshan Chattopadhyay,
Avishay Tal,
Shachar Lovett,
Pooya Hatami
https://eccc.weizmann.ac.il/report/2018/155A recent work of Chattopadhyay et al. (CCC 2018) introduced a new framework for the design of pseudorandom generators for Boolean functions. It works under the assumption that the Fourier tails of the Boolean functions are uniformly bounded for all levels by an exponential function. In this work, we design an alternative pseudorandom generator that only requires bounds on the second level of the Fourier tails. It is based on a derandomization of the work of Raz and Tal (ECCC 2018) who used the above framework to obtain an oracle separation between BQP and PH.
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.Sat, 08 Sep 2018 15:40:48 +0300https://eccc.weizmann.ac.il/report/2018/155