Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
From MaRDI portal
(Redirected from Publication:430845)
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)
Recommendations
Cites work
- scientific article; zbMATH DE number 5485478 (Why is no real title available?)
- scientific article; zbMATH DE number 1306886 (Why is no real title available?)
- scientific article; zbMATH DE number 2019636 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- scientific article; zbMATH DE number 1857655 (Why is no real title available?)
- scientific article; zbMATH DE number 5485587 (Why is no real title available?)
- #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)- scientific article; zbMATH DE number 7650416 (Why is no real title available?)
- Circuit size relative to pseudorandom oracles
- scientific article; zbMATH DE number 1689047 (Why is no real title available?)
- 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
- Robustness of average-case meta-complexity via pseudorandomness
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity
- Fine-grained derandomization: from problem-centric to resource-centric complexity
- 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
- Pseudorandom Generators and Typically-Correct Derandomization
- scientific article; zbMATH DE number 7754310 (Why is no real title available?)
- scientific article; zbMATH DE number 2019636 (Why is no real title available?)
- Pseudorandom functions in \(\text{TC}^0\) and cryptographic limitations to proving lower bounds
- Generation of all randomizations using circuits
- Typically-correct derandomization for small time and space
- (Nondeterministic) hardness vs. non-malleability
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)
