Document Open Access Logo

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

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

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.22.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Eshan Chattopadhyay
  • Department of Computer Science, Cornell University, 107 Hoy Rd, Ithaca, NY, USA
Pooya Hatami
  • Department of Computer Science, University of Texas at Austin, 2317 Speedway, Austin, TX, USA
Shachar Lovett
  • Department of Computer Science, University of California San Diego, La Jolla, CA, USA
Avishay Tal
  • Department of Computer Science, Stanford University, 353 Serra Mall, Stanford, CA, USA

Funding

  • Hatami, Pooya: Supported by a Simons Investigator Award #409864, David Zuckerman.
  • Lovett, Shachar: Supported by NSF grant CCF-1614023.
  • Tal, Avishay: Supported by a Motwani Postdoctoral Fellowship and by NSF grant CCF-1763299.

Cite As Get BibTex

Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal. Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.22

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Derandomization
  • Pseudorandom generator
  • Explicit construction
  • Random walk
  • Small-depth circuits with parity gates

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Boaz Barack and Jarosław Błasiok. On the Raz-Tal oracle separation of BQP and PH, 2018. URL: https://windowsontheory.org/2018/06/17/on-the-raz-tal-oracle-separation-of-bqp-and-ph/.
  2. Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett. Pseudorandom Generators from Polarizing Random Walks. In 33rd Computational Complexity Conference, CCC 2018, pages 1:1-1:21, 2018. Google Scholar
  3. Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, and Avishay Tal. Improved pseudorandomness for unordered branching programs through local monotonicity. In STOC, pages 363-375. ACM, 2018. Google Scholar
  4. Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola. On Beating the Hybrid Argument. Theory of Computing, 9:809-843, 2013. Google Scholar
  5. Leon Isserlis. On a formula for the product-moment coefficient of any order of a normal frequency distribution in any number of variables. Biometrika, 12(1/2):134-139, 1918. Google Scholar
  6. Daniel M. Kane. A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting. In Conference on Computational Complexity, volume 33 of LIPIcs, pages 567-581, 2015. Google Scholar
  7. Swastik Kopparty. On the complexity of powering in finite fields. In STOC, pages 489-498. ACM, 2011. Google Scholar
  8. Peter Mörters and Yuval Peres. Brownian motion, volume 30. Cambridge University Press, 2010. Google Scholar
  9. Ran Raz and Avishay Tal. Oracle Separation of BQP and PH. Electronic Colloquium on Computational Complexity (ECCC), 25:107, 2018. Google Scholar
  10. Alexander A Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333-338, 1987. Google Scholar
  11. R. Smolensky. On representations by low-degree polynomials. In FOCS, pages 130-138, 1993. Google Scholar
  12. Roman Smolensky. Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In STOC, pages 77-82. ACM, 1987. Google Scholar
  13. Amnon Ta-Shma. Explicit, almost optimal, epsilon-balanced codes. In STOC, pages 238-251, 2017. Google Scholar
  14. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1-336, 2012. Google Scholar
  15. Emanuele Viola. Guest Column: correlation bounds for polynomials over 0 1. ACM SIGACT News, 40(1):27-44, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact