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

DOI10.1007/S00037-011-0019-ZzbMATH Open1242.68108OpenAlexW2036322072MaRDI QIDQ430845FDOQ430845

Authors: Jeff Kinne, Dieter Van Melkebeek, Ronen Shaltiel 

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

Recommendations

• Pseudorandom Generators and Typically-Correct Derandomization
• Can every randomized algorithm be derandomized?
• Hardness vs randomness
• Pseudorandomness when the odds are against you
• scientific article; zbMATH DE number 2019636

zbMATH Keywords

randomized algorithmspseudorandom generatorscircuit lower boundstypically-correct derandomization

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (20)

• Robustness of average-case meta-complexity via pseudorandomness
• Pseudorandom functions in \(\text{TC}^0\) and cryptographic limitations to proving lower bounds
• Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
• Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly
• On pseudorandomness and resource-bounded measure
• Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
• Title not available (Why is that?)
• Improved Extractors for Recognizable and Algebraic Sources
• Title not available (Why is that?)
• Title not available (Why is that?)
• (Nondeterministic) hardness vs. non-malleability
• Circuit size relative to pseudorandom oracles
• Title not available (Why is that?)
• Deterministic polynomial identity tests for multilinear bounded-read formulae
• The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity
• Pseudorandom Generators and Typically-Correct Derandomization
• Generation of all randomizations using circuits
• Title not available (Why is that?)
• Typically-correct derandomization for small time and space
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution

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

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