Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
From MaRDI portal
Publication:3149879
DOI10.1137/S0097539700389652zbMath1016.68060OpenAlexW2083237534MaRDI 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
learning theoryderandomizationinteractive proofsgraph isomorphismpseudorandomnessunique satisfiabilityArthur-Merlin gamesuniversal traversal sequenceshardness versus randomnessrigid matrices
Related Items
Randomized and Symmetric Catalytic Computation, The Untold Story of $$\mathsf {SBP}$$, NL-printable sets and nondeterministic Kolmogorov complexity, Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, Unnamed Item, Circuit lower bounds from learning-theoretic approaches, Quantified Derandomization: How to Find Water in the Ocean, Nonuniform ACC Circuit Lower Bounds, Nonuniform reductions and NP-completeness, A thirty year old conjecture about promise problems, Is Valiant-Vazirani's isolation probability improvable?, The size of SPP, On approximating the eigenvalues of stochastic matrices in probabilistic logspace, Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, Infeasibility of instance compression and succinct PCPs for NP, Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error, (Nondeterministic) hardness vs. non-malleability, The power of natural properties as oracles, A remark on pseudo proof systems and hard instances of the satisfiability problem, Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\), Some games on Turing machines and power from random strings, Paradigms for Unconditional Pseudorandom Generators, Unnamed Item, Pseudorandom generators, typically-correct derandomization, and circuit lower bounds, Catalytic space: non-determinism and hierarchy, Unnamed Item, Low-depth witnesses are easy to find, Unnamed Item, Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds, Arthur and Merlin as oracles, Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma, Relations between average-case and worst-case complexity, On Pseudodeterministic Approximation Algorithms., NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES, The complexity of explicit constructions, NL-printable sets and Nondeterministic Kolmogorov Complexity, Lower bounds for non-black-box zero knowledge, Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games, On zero error algorithms having oracle access to one query, Arthur and Merlin as Oracles, Unnamed Item, Unnamed Item, Natural Proofs versus Derandomization, Unnamed Item, On the Optimal Compression of Sets in PSPACE, Unnamed Item, Randomness and Intractability in Kolmogorov Complexity, Typically-correct derandomization for small time and space, Derandomizing Isolation in Space-Bounded Settings, Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace, Efficient Construction of Rigid Matrices Using an NP Oracle, On optimal language compression for sets in PSPACE/poly, Quantum commitments from complexity assumptions, The complexity of estimating min-entropy
