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

DOI10.4230/LIPIcs.ITCS.2019.22OpenAlexW2911869889MaRDI QIDQ5090395

Avishay Tal, Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett

Publication date: 18 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/10115/pdf/LIPIcs-ITCS-2019-22.pdf/

zbMATH Keywords

random walkderandomizationpseudorandom generatorexplicit constructionsmall-depth circuits with parity gates

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (8)

Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ Parity helps to compute majority ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Quantum versus randomized communication complexity, with efficient players

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Explicit, almost optimal, epsilon-balanced codes
• Oracle separation of BQP and PH
• Improved pseudorandomness for unordered branching programs through local monotonicity
• On the complexity of powering in finite fields
• Brownian Motion

This page was built for publication: Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates