License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2019.22
URN: urn:nbn:de:0030-drops-101150
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10115/
Go to the corresponding LIPIcs Volume Portal

Chattopadhyay, Eshan ; Hatami, Pooya ; Lovett, Shachar ; Tal, Avishay

Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates

pdf-format:
LIPIcs-ITCS-2019-22.pdf (0.5 MB)

Abstract

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 F_2. If true, it would imply an efficient pseudorandom generator for 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.

BibTeX - Entry

@InProceedings{chattopadhyay_et_al:LIPIcs:2018:10115,
  author =	{Eshan Chattopadhyay and Pooya Hatami and Shachar Lovett and Avishay Tal},
  title =	{{Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates}},
  booktitle =	{10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  pages =	{22:1--22:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{124},
  editor =	{Avrim Blum},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10115},
  URN =		{urn:nbn:de:0030-drops-101150},
  doi =		{10.4230/LIPIcs.ITCS.2019.22},
  annote =	{Keywords: Derandomization, Pseudorandom generator, Explicit construction, Random walk, Small-depth circuits with parity gates}
}

Keywords: Derandomization, Pseudorandom generator, Explicit construction, Random walk, Small-depth circuits with parity gates
Collection: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Issue Date: 2018
Date of publication: 08.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI