ECCC-Report TR98-075https://eccc.weizmann.ac.il/report/1998/075Comments and Revisions published for TR98-075en-usThu, 17 Dec 1998 16:46:57 +0200
Paper TR98-075
| Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. |
Adam Klivans,
Dieter van Melkebeek
https://eccc.weizmann.ac.il/report/1998/075We establish hardness versus randomness trade-offs for a
broad class of randomized procedures. In particular, we create efficient
nondeterministic simulations of bounded round Arthur-Merlin games using
a language in exponential time that cannot be decided by polynomial
size oracle circuits with access to satisfiability. We show that every
language with a bounded round Arthur-Merlin game has subexponential
size membership proofs for infinitely many input lengths unless the
polynomial-time hierarchy collapses. This provides the first strong
evidence that graph nonisomorphism has subexponential size proofs.
We set up a general framework for derandomization which encompasses more
than the traditional model of randomized computation. For a randomized
procedure to fit within this framework, we only require that for any fixed
input the complexity of checking whether the procedure succeeds on a given
random bit sequence is not too high. We then apply our derandomization
technique to four fundamental complexity theoretic constructions:
1. The Valiant-Vazirani random hashing technique which prunes the
number of satisfying assignments of a Boolean formula to one, and related
procedures like computing satisfying assignments to Boolean formulas
non-adaptively given access to an oracle for satisfiability.
2. The algorithm of Bshouty et al. for learning Boolean circuits.
3. Constructing matrices with high rigidity. 4. Constructing
polynomial-size universal traversal sequences.
We also show that if linear space requires exponential size circuits, then
space bounded randomized computations can be simulated deterministically
with only a constant factor overhead in space.
Thu, 17 Dec 1998 16:46:57 +0200https://eccc.weizmann.ac.il/report/1998/075