Pseudorandomness from shrinkage

DOI10.1145/3230630MaRDI QIDQ5244384zbMATH OpenOpenAlexWikidataFDO

Authors Russell Impagliazzo, Raghu Meka, David Zuckerman

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

average-case lower boundsrandom restrictionsshrinkage

Mathematics Subject Classification ID

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

Recommendations

• Improved pseudorandom generators for depth 2 circuits
• Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits
• Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits

Cited in

(29)

• Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries
• Fourier concentration from shrinkage
• Mining circuit lower bound proofs for meta-algorithms
• Satisfiability algorithms and lower bounds for Boolean formulas over finite bases
• Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• An improved deterministic \#SAT algorithm for small De Morgan formulas
• Improved pseudorandom generators for depth 2 circuits
• Bounded independence plus noise fools products
• Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits
• Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• Circuit lower bounds for MCSP from local pseudorandom generators
• Fourier bounds and pseudorandom generators for product tests
• 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
• Amplification and Derandomization without Slowdown
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• Sampling lower bounds: Boolean average-case and permutations
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits
• Improved pseudorandom generators from pseudorandom multi-switching lemmas
• Algorithms and lower bounds for comparator circuits from shrinkage
• Paradigms for Unconditional Pseudorandom Generators
• One-tape Turing machine and branching program lower bounds for MCSP
• Towards stronger depth lower bounds
• One-tape Turing machine and branching program lower bounds for MCSP
• Negation-limited formulas

This page was built for publication: Pseudorandomness from shrinkage

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