# BPP has subexponential time simulations unlessEXPTIME has publishable proofs

@article{Babai2005BPPHS, title={BPP has subexponential time simulations unlessEXPTIME has publishable proofs}, author={L{\'a}szl{\'o} Babai and Lance Fortnow and Noam Nisan and Avi Wigderson}, journal={computational complexity}, year={2005}, volume={3}, pages={307-318} }

AbstractWe show thatBPP can be simulated in subexponential time for infinitely many input lengths unless exponential timeℴ collapses to the second level of the polynomial-time hierarchy.ℴ has polynomial-size circuits andℴ has publishable proofs (EXPTIME=MA).
We also show thatBPP is contained in subexponential time unless exponential time has publishable proofs for infinitely many input lengths. In addition, we showBPP can be simulated in subexponential time for infinitely many input lengths… Expand

#### Topics from this paper

#### 89 Citations

Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds

- Computer Science, Mathematics
- 2010 IEEE 25th Annual Conference on Computational Complexity
- 2010

If Arthur-Merlin protocols can be derandomized, then there is a language computable in deterministic exponential-time with access to an NP oracle that requires circuits of exponential size and the lower bound in the conclusion of the theorem suffices to construct pseudorandom generators with exponential stretch. Expand

Holographic proofs and derandomization

- Mathematics
- 18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings.
- 2003

We derive a stronger consequence of EXP having polynomial-size circuits than was known previously, namely that there is a simulation of P in MAPOLYLOG that fools all deterministic polynomial-time… Expand

Pseudorandomness for Approximate Counting and Sampling

- Computer Science, Mathematics
- Computational Complexity Conference
- 2005

The goal of this paper is to derandomize computational procedures under the weakest possible assumptions, and uses the "boosting" theorem and hashing techniques to construct two new primitives that are regarded as the natural pseudorandom objects associated with approximate counting and sampling of NP-witnesses. Expand

Circuit Complexity, Proof Complexity, and Polynomial Identity Testing

- Computer Science, Mathematics
- J. ACM
- 2018

A new and natural algebraic proof system, whose complexity measure is essentially the algebraic circuit size of Nullstellensatz certificates, that shows that any super-polynomial lower bound on any Boolean tautology in this proof system implies that the permanent does not have polynomial-size algebraic circuits. Expand

Uniform Derandomization from Pathetic Lower Bounds

- Mathematics, Computer Science
- APPROX-RANDOM
- 2010

This work presents two instances where "pathetic" lower bounds of the form n1+e would suffice to derandomize interesting classes of probabilistic algorithms. Expand

Worst-Case to Average-Case Reductions Revisited

- Mathematics, Computer Science
- APPROX-RANDOM
- 2007

Under a mild derandomization assumption, the worst-case hardness of NP implies the average- case hardness of NTIME(f(n)) (under the uniform distribution) where fis computable in quasi-polynomial time. Expand

If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances

- Mathematics, Computer Science
- 20th Annual IEEE Conference on Computational Complexity (CCC'05)
- 2005

It is shown that there is a fixed distribution on instances of NP-complete languages, that is samplable in quasi-polynomial time and is hard for all probabilistic polynomial-time algorithms (unless NP is easy in the worst case). Expand

On TC0 Lower Bounds for the Permanent

- Mathematics, Computer Science
- COCOON
- 2012

This paper proves a new parameterized lower bound that includes each of the previous results as sub-cases for the permanent and implies that the permanent does not have Boolean threshold circuits of the following kinds. Expand

Hardness Hypotheses, Derandomization, and Circuit Complexity

- Computer Science, Mathematics
- computational complexity
- 2008

The NP-machine hypothesis becomes the weakest known uniform hardness hypothesis that derandomizes AM and is unify previous work by showing that several derandomizations and circuit-size lower bounds that are known to follow from the first two hypotheses also followed from the NP- machine hypothesis. Expand

If NP Languages are Hard on the Worst-Case Then It is Easy to Find Their Hard Instances

- Mathematics, Computer Science
- Computational Complexity Conference
- 2005

It is shown that there is a fixed distribution on instances of NP-complete languages, that is samplable in quasi-polynomial time and is hard for all probabilistic polynomial time algorithms (unless NP is easy in the worst-case). Expand

#### References

SHOWING 1-10 OF 62 REFERENCES

Non-deterministic exponential time has two-prover interactive protocols

- Computer Science
- computational complexity
- 2005

It is shown that the class of languages having tow-prover interactive proof systems is nondeterministic exponential time and that to prove membership in languages inEXP, the honest provers need the power ofEXP only. Expand

Multi-prover interactive proofs: how to remove intractability assumptions

- Mathematics, Computer Science
- STOC '88
- 1988

It is proved that all NP languages have perfect zero-knowledge proof-systems in this model, without making any intractability assumptions, and its properties and applicability to cryptography are examined. Expand

Hardness vs Randomness

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1994

A new construction of a pseudorandom bit generator that stretches a short string of truly random bits into a long string that looks random to any algorithm from a complexity class C using an arbitrary function that is hard for C is presented. Expand

Some connections between nonuniform and uniform complexity classes

- Mathematics, Computer Science
- STOC '80
- 1980

This work aims to understand when nonuniform upper bounds can be used to obtain uniform upper bounds, and how to relate it to more common notions. Expand

Sparse Sets in NP-P: EXPTIME versus NEXPTIME

- Computer Science, Mathematics
- Inf. Control.
- 1985

The paper exploits the recently discovered upward separation method and uses relativization techniques to determine logical possibilities, limitations of these proof techniques, and exhibits one of the first natural structural differences between relativized NP and CoNP. Expand

Sparse sets in NP-P: Exptime versus nexptime

- Mathematics, Computer Science
- STOC
- 1983

The paper exploits the recently discovered upward separation method and uses relativization techniques to determine logical possibilities, limitations of these proof techniques, and, for the first time, to exhibit structural differences between relativized NP and CoNP. Expand

Hiding Instances in Multioracle Queries

- Computer Science
- STACS
- 1990

It is shown that, if f is an NP-hard function, A cannot query a single oracle B while hiding all but the size of the instance, assuming that the polynomial hierarchy does not collapse. Expand

Arithmetization: A new method in structural complexity theory

- Mathematics, Computer Science
- computational complexity
- 2005

A technique of arithmetization of the process of computation is introduced in order to obtain novel characterizations of certain complexity classes viamultivariate polynomials, demonstrating the applicability of this technique to classical complexity classes. Expand

On Relativized Exponential and Probabilistic Complexity Classes

- Mathematics, Computer Science
- Inf. Control.
- 1986

An oracle X is constructed such that the exponential complexity class Δ EP, X 2 equals the probabilistic class R(R( X )). This shows that it will be difficult to prove that Δ EP 2 is different from… Expand

On the existence of pseudorandom generators

- Mathematics, Computer Science
- [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science
- 1988

It is shown that if aRegular functions in which every image of a k-bit string has the same number of preimages of length k are considered, then pseudorandom generators do exist, and assuming the intractability of general factoring, it can be proved that they do exist. Expand