Pseudorandomness for Read-Once Formulas

DOI10.1109/FOCS.2011.57MaRDI QIDQ5494968zbMATH OpenFDO

Authors Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/FOCS.2011.57

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cited in

(9)

• A dichotomy for local small-bias generators
• Cryptographic hardness of random local functions. Survey
• Pseudorandom generators for combinatorial checkerboards
• Bounded independence plus noise fools products
• Fourier bounds and pseudorandom generators for product tests
• Near-optimal pseudorandom generators for constant-depth read-once formulas
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• More on bounded independence plus noise: pseudorandom generators for read-once polynomials
• Paradigms for Unconditional Pseudorandom Generators

This page was built for publication: Pseudorandomness for Read-Once Formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5494968)