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

DOI10.1137/S0097539700389652zbMath1016.68060MaRDI QIDQ3149879

Dieter van Melkebeek, Adam R. Klivans

Publication date: 29 September 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

learning theory; derandomization; interactive proofs; graph isomorphism; pseudorandomness; unique satisfiability; Arthur-Merlin games; universal traversal sequences; hardness versus randomness; rigid matrices

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C99: Graph theory

Related Items

NL-printable sets and Nondeterministic Kolmogorov Complexity, NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES, Quantum commitments from complexity assumptions, The complexity of estimating min-entropy, Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, Is Valiant-Vazirani's isolation probability improvable?, Pseudorandom generators, typically-correct derandomization, and circuit lower bounds, Low-depth witnesses are easy to find, The size of SPP, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, Infeasibility of instance compression and succinct PCPs for NP, Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds, Arthur and Merlin as oracles, The complexity of explicit constructions, Relations between average-case and worst-case complexity, On optimal language compression for sets in PSPACE/poly, NL-printable sets and nondeterministic Kolmogorov complexity, Lower bounds for non-black-box zero knowledge, On zero error algorithms having oracle access to one query, Natural Proofs versus Derandomization, On the Optimal Compression of Sets in PSPACE, Nonuniform ACC Circuit Lower Bounds, Arthur and Merlin as Oracles