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

zbMATH Keywords

graph isomorphismlownessSPPcounting classes

Mathematics Subject Classification ID

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)

Recommendations

• Graph isomorphism is low for PP
• Graph isomorphism is low for PP
• GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMORPHISM PROBLEM
• On the Hardness of Graph Isomorphism
• Graph isomorphism is in the low hierarchy

Cites work

• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 1335894 (Why is no real title available?)
• scientific article; zbMATH DE number 475362 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 512806 (Why is no real title available?)
• scientific article; zbMATH DE number 3223737 (Why is no real title available?)
• scientific article; zbMATH DE number 3341276 (Why is no real title available?)
• A low and a high hierarchy within NP
• A note on the graph isomorphism counting problem
• A taxonomy of complexity classes of functions
• An oracle builder's toolkit
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Bounded Round Interactive Proofs in Finite Groups
• Computing functions with parallel queries to NP
• Counting Complexity of Solvable Black-Box Group Problems
• Does co-NP have short interactive proofs ?
• EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
• Graph isomorphism is low for PP
• Group-theoretic algorithms and graph isomorphism
• PP-lowness and a simple definition of AWPP
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Solvable black-box group problems are low for PP
• The complexity of computing the permanent
• The complexity of promise problems with applications to public-key cryptography
• Turing machines with few accepting computations and low sets for PP

Cited in

(24)

• SZK proofs for black-box group problems
• Graph isomorphism is low for PP
• Representing Groups on Graphs
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• An oracle builder's toolkit
• Count-free Weisfeiler-Leman and group isomorphism
• No easy puzzles: hardness results for jigsaw puzzles
• Complexity results in graph reconstruction
• LWPP and WPP are not uniformly gap-definable
• On the isomorphism of graphs having some eigenvalues of moderate multiplicity
• Computational complexity of computing a partial solution for the graph automorphism problems
• The complexity of symmetric Boolean parity Holant problems (extended abstract)
• Computational indistinguishability between quantum states and its cryptographic application
• The isomorphism problem for \(k\)-trees is complete for logspace
• On the power of counting the total number of computation paths of NPTMs
• SPN graphs: when copositive = SPN
• On the complexity of identifying strongly regular graphs
• The Isomorphism Problem for k-Trees Is Complete for Logspace
• On the Complexity of the Hidden Subgroup Problem
• Graph isomorphism is low for PP
• Minimum circuit size, graph isomorphism, and related problems
• On the complexity of matroid isomorphism problem
• The size of SPP
• The saga of minimum spanning trees

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)