\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
From MaRDI portal
Publication:1321029
DOI10.1007/BF01275486zbMath0802.68054OpenAlexW2998808137WikidataQ55887620 ScholiaQ55887620MaRDI QIDQ1321029
Avi Wigderson, László Babai, Noam Nisan, Lance J. Fortnow
Publication date: 8 May 1994
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01275486
Related Items
New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes., In search of an easy witness: Exponential time vs. probabilistic polynomial time., Uniformly hard languages., Hardness vs randomness, A downward translation in the polynomial hierarchy, Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, Unnamed Item, Circuit lower bounds from learning-theoretic approaches, Nonuniform ACC Circuit Lower Bounds, Nonuniform reductions and NP-completeness, Average-case intractability vs. worst-case intractability, Results on resource-bounded measure, On locally decodable codes, self-correctable codes, and \(t\)-private PIR, Uniform derandomization from pathetic lower bounds, Pseudorandom generators for combinatorial checkerboards, Worst-Case to Average-Case Reductions for Subclasses of P, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, Hardness amplification within NP against deterministic algorithms, Erasures versus errors in local decoding and property testing, The power of natural properties as oracles, Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\), Some games on Turing machines and power from random strings, Paradigms for Unconditional Pseudorandom Generators, Unnamed Item, Pseudorandom generators, typically-correct derandomization, and circuit lower bounds, Local List Recovery of High-Rate Tensor Codes and Applications, Unnamed Item, On derandomizing Yao's weak-to-strong OWF construction, Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds, Weak derandomization of weak algorithms: explicit versions of Yao's lemma, Complexity of hard-core set proofs, Hard sets are hard to find, Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma, Foundations of Homomorphic Secret Sharing, Relations between average-case and worst-case complexity, If NP has polynomial-size circuits, then MA=AM, NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES, Limits on the Computational Power of Random Strings, Collapsing and separating completeness notions under average-case and worst-case hypotheses, Avoiding simplicity is complex, Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games, Fourier concentration from shrinkage, Local Property Reconstruction and Monotonicity, Pseudorandom generators without the XOR lemma, Unnamed Item, Easiness assumptions and hardness tests: Trading time for zero error, Hardness amplification within NP, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Pseudo-random generators for all hardnesses, Natural Proofs versus Derandomization, Efficient learning algorithms yield circuit lower bounds, Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification, ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS, Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification, Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More), Unnamed Item, Randomness and Intractability in Kolmogorov Complexity, Typically-correct derandomization for small time and space, A Downward Collapse within the Polynomial Hierarchy, Does Looking Inside a Circuit Help, Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly, High-rate codes with sublinear-time decoding, A combination of testability and decodability by tensor products, Unnamed Item, Randomness vs time: Derandomization under a uniform assumption
Cites Work
- Arithmetization: A new method in structural complexity theory
- Non-deterministic exponential time has two-prover interactive protocols
- One way functions and pseudorandom generators
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Sparse sets in NP-P: EXPTIME versus NEXPTIME
- On relativized exponential and probabilistic complexity classes
- The Knowledge Complexity of Interactive Proof Systems
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Algebraic methods for interactive proof systems
- IP = PSPACE
- Designing programs that check their work
- Unnamed Item
