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