Pseudorandom generators, typically-correct derandomization, and circuit lower bounds

DOI10.1007/s00037-011-0019-zzbMath1242.68108OpenAlexW2036322072MaRDI QIDQ430845

Jeff Kinne, Ronen Shaltiel, Dieter van Melkebeek

Publication date: 26 June 2012

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-011-0019-z

zbMATH Keywords

randomized algorithmspseudorandom generatorscircuit lower boundstypically-correct derandomization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Related Items (8)

(Nondeterministic) hardness vs. non-malleability ⋮ Unnamed Item ⋮ Deterministic polynomial identity tests for multilinear bounded-read formulae ⋮ Improved Extractors for Recognizable and Algebraic Sources ⋮ Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games ⋮ Typically-correct derandomization for small time and space ⋮ Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly ⋮ Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weak derandomization of weak algorithms: explicit versions of Yao's lemma
• Pseudorandom bits for constant depth circuits
• Derandomizing Arthur-Merlin games using hitting sets
• Exposure-resilient extractors and the derandomization of probabilistic sublinear time
• Relativized circuit complexity
• Private vs. common random bits in communication complexity
• On read-once vs. multiple access to randomness in logspace
• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Hardness vs randomness
• Randomness vs time: Derandomization under a uniform assumption
• Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
• The complexity of constructing pseudorandom generators from hard functions
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Pseudorandomness for approximate counting and sampling
• Pseudorandomness and average-case complexity via uniform reductions
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Circuit-size lower bounds and non-reducibility to sparse sets
• PP is as Hard as the Polynomial-Time Hierarchy
• Simple extractors for all min-entropies and a new pseudorandom generator
• Undirected connectivity in log-space
• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
• IP = PSPACE
• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
• Holographic Proofs and Derandomization
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Easiness assumptions and hardness tests: Trading time for zero error

This page was built for publication: Pseudorandom generators, typically-correct derandomization, and circuit lower bounds