Graph Isomorphism is in SPP
DOI10.1016/J.IC.2006.02.002zbMATH Open1110.68090DBLPjournals/iandc/ArvindK06OpenAlexW2020273705WikidataQ55889735 ScholiaQ55889735MaRDI QIDQ2495656FDOQ2495656
Authors: Vikraman Arvind, Piyush P. Kurur 
Publication date: 30 June 2006
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2006.02.002
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- A taxonomy of complexity classes of functions
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- The complexity of computing the permanent
- Title not available (Why is that?)
- Title not available (Why is that?)
- Group-theoretic algorithms and graph isomorphism
- Title not available (Why is that?)
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Does co-NP have short interactive proofs ?
- The complexity of promise problems with applications to public-key cryptography
- Computing functions with parallel queries to NP
- Title not available (Why is that?)
- A low and a high hierarchy within NP
- Title not available (Why is that?)
- Title not available (Why is that?)
- A note on the graph isomorphism counting problem
- Solvable black-box group problems are low for PP
- EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
- Title not available (Why is that?)
- Turing machines with few accepting computations and low sets for PP
- An oracle builder's toolkit
- Graph isomorphism is low for PP
- Bounded Round Interactive Proofs in Finite Groups
- Counting Complexity of Solvable Black-Box Group Problems
- Title not available (Why is that?)
- PP-lowness and a simple definition of AWPP
Cited In (23)
- Minimum Circuit Size, Graph Isomorphism, and Related Problems
- No easy puzzles: hardness results for jigsaw puzzles
- Title not available (Why is that?)
- The isomorphism problem for \(k\)-trees is complete for logspace
- On the Complexity of the Hidden Subgroup Problem
- The size of SPP
- An oracle builder's toolkit
- SPN graphs: when copositive = SPN
- The saga of minimum spanning trees
- Complexity results in graph reconstruction
- Computational complexity of computing a partial solution for the graph automorphism problems
- LWPP and WPP are not uniformly gap-definable
- On the isomorphism of graphs having some eigenvalues of moderate multiplicity
- The Isomorphism Problem for k-Trees Is Complete for Logspace
- Computational indistinguishability between quantum states and its cryptographic application
- On the power of counting the total number of computation paths of NPTMs
- On the complexity of matroid isomorphism problem
- Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
- Representing Groups on Graphs
- SZK proofs for black-box group problems
- Graph isomorphism is low for PP
- The complexity of symmetric Boolean parity Holant problems (extended abstract)
- Count-free Weisfeiler-Leman and group isomorphism
This page was built for publication: Graph Isomorphism is in SPP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2495656)
