Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-155 | 8th September 2018 15:35

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


Authors: Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal
Publication: 8th September 2018 15:40
Downloads: 2962


A 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.

ISSN 1433-8092 | Imprint