__
TR98-075 | 9th December 1998 00:00
__

#### Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.

**Abstract:**
We 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.