Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses

Authors:
  • AKAdam R. Klivans
    Adam R. Klivans
  • DMDieter van Melkebeek
    Dieter van Melkebeek
Top Cited Papers
Publisher website
Google Scholar
Abstract
Traditional hardness versus randomness results focus on time-efficient randomized decision procedures. We generalize these trade-offs to a much wider class of randomized processes. We work out various applications, most notably to derandomizing Arthur-Merlin games. We show that every language with a bounded round Arthur-Merlin game has subexponential size membership proofs for infinitely many input lengths unless exponential time coincides with the third level of the polynomial-time hierarchy (and hence the polynomial-time hierarchy collapses). Since the graph nonisomorphism problem has a bounded round Arthur-Merlin game, this provides the first strong evidence that graph nonisomorphism has subexponential size proofs. We also establish hardness versus randomness trade-offs for space bounded computation.

This publication has 40 references indexed in Scilit: