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

Adam R. Klivans, Dieter van Melkebeek

Browse the full STOC paper archive.