Pseudorandomness from Shrinkage

DOI10.1145/3230630zbMath1427.68096OpenAlexW2938685469WikidataQ128091772 ScholiaQ128091772MaRDI QIDQ5244384

Russell Impagliazzo, David Zuckerman, Raghu Meka

Publication date: 21 November 2019

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3230630

zbMATH Keywords

shrinkagerandom restrictionsaverage-case lower bounds

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (22)

Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries ⋮ An improved deterministic \#SAT algorithm for small De Morgan formulas ⋮ Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits ⋮ Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases ⋮ Algorithms and lower bounds for comparator circuits from shrinkage ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound ⋮ Amplification and Derandomization without Slowdown ⋮ Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs ⋮ Bounded Independence Plus Noise Fools Products ⋮ Fourier concentration from shrinkage ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Negation-limited formulas ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits ⋮ Mining circuit lower bound proofs for meta-algorithms

This page was built for publication: Pseudorandomness from Shrinkage