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
(21)- Robustness of average-case meta-complexity via pseudorandomness
- Pseudorandom functions in \(\text{TC}^0\) and cryptographic limitations to proving lower bounds
- 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
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- On pseudorandomness and resource-bounded measure
- scientific article; zbMATH DE number 7754310 (Why is no real title available?)
- Improved Extractors for Recognizable and Algebraic Sources
- scientific article; zbMATH DE number 2019636 (Why is no real title available?)
- (Nondeterministic) hardness vs. non-malleability
- Circuit size relative to pseudorandom oracles
- Deterministic polynomial identity tests for multilinear bounded-read formulae
- Uniform black-box separations via non-malleable extractors
- scientific article; zbMATH DE number 7650416 (Why is no real title available?)
- 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
- scientific article; zbMATH DE number 1689047 (Why is no real title available?)
- 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)
