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)

Full work available at URL: https://doi.org/10.1137/s0097539700389652

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

Unnamed Item, Unnamed Item, NL-printable sets and Nondeterministic Kolmogorov Complexity, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Randomized and Symmetric Catalytic Computation, The Untold Story of $$\mathsf {SBP}$$, Quantified Derandomization: How to Find Water in the Ocean, Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space, A remark on pseudo proof systems and hard instances of the satisfiability problem, Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma, On Pseudodeterministic Approximation Algorithms., Randomness and Intractability in Kolmogorov Complexity, Typically-correct derandomization for small time and space, Derandomizing Isolation in Space-Bounded Settings, NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES, Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace, Efficient Construction of Rigid Matrices Using an NP Oracle, (Nondeterministic) hardness vs. non-malleability, The power of natural properties as oracles, Quantum commitments from complexity assumptions, The complexity of estimating min-entropy, Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, A thirty year old conjecture about promise problems, 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, Catalytic space: non-determinism and hierarchy, Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games, Nonuniform reductions and NP-completeness, On optimal language compression for sets in PSPACE/poly, NL-printable sets and nondeterministic Kolmogorov complexity, On approximating the eigenvalues of stochastic matrices in probabilistic logspace, Lower bounds for non-black-box zero knowledge, On zero error algorithms having oracle access to one query, Circuit lower bounds from learning-theoretic approaches, Natural Proofs versus Derandomization, On the Optimal Compression of Sets in PSPACE, Unnamed Item, Nonuniform ACC Circuit Lower Bounds, Arthur and Merlin as Oracles