Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses

DOI10.1145/301250.301428zbMath1345.68174OpenAlexW1979479253MaRDI QIDQ2819595

Dieter van Melkebeek, Adam R. Klivans

Publication date: 29 September 2016

Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/301250.301428

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Complexity of proofs (03F20)

Related Items

In search of an easy witness: Exponential time vs. probabilistic polynomial time., A zero-one law for RP and derandomization of AM if NP is not small, \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\), Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings, Robust simulations and significant separations, Isolation, matching, and counting uniform and nonuniform upper bounds, Martingale families and dimension in P, Baire categories on small complexity classes and meager-comeager laws, Pseudorandom generators without the XOR lemma, Easiness assumptions and hardness tests: Trading time for zero error, Pseudo-random generators for all hardnesses, Interactive and probabilistic proof-checking