AbstractWe show that Graph Isomorphism is in the complexity class SPP, and hence it is in ⊕P (in fact, in ModkP for each k⩾2). These inclusions for Graph Isomorphism were not known prior to membership in SPP. We derive this result as a corollary of a more general result: we show that a generic problem FIND-GROUP has an FPSPP algorithm. This general result has other consequences: for example, it follows that the hidden subgroup problem for permutation groups, studied in the context of quantum algorithms, has an FPSPP algorithm. Also, some other algorithmic problems over permutation groups known to be at least as hard as Graph Isomorphism (e.g., coset intersection) are in SPP, and thus in ModkP for each k⩾2
Derandomization techniques are used to show that at least one of the following holds regarding the s...
We study the computational power of deciding whether a given truth-table can be described by a circu...
Graph Isomorphism is one of the very few classical problems in NP of unsettled complexity status. Th...
AbstractWe show that Graph Isomorphism is in the complexity class SPP, and hence it is in ⊕P (in fac...
We show that Graph Isomorphism is in the complexity class SPP, and hence it is in ⊕P (in fact, it is...
AbstractWe present eight group-theoretic problems in NP one of which is a reformulation of graph iso...
We study the non-uniform complexity of the Graph Isomorphism (GI) and Graph Automorphism (GA) proble...
Graph isomorphism (GI) is one of the few remaining problems in NP whose complexity status couldn’t b...
AbstractIt is shown that the graph isomorphism problem is located in level L2p of the low hierarchy ...
In this paper we study some classical complexity-theoretic questions regarding Group Isomorphism (Gp...
In this paper I propose a polynomial time algorithm for the Graph Isomorphism problem, which always...
A recent result has shown that the graph isomorphism problem can be solved in quasi-polynomial time,...
AbstractAn open question is the computational complexity of recognizing when two graphs are isomorph...
AbstractDerandomization techniques are used to show that at least one of the following holds regardi...
AbstractWe investigate the computational complexity of the following restricted variant of Subgraph ...
Derandomization techniques are used to show that at least one of the following holds regarding the s...
We study the computational power of deciding whether a given truth-table can be described by a circu...
Graph Isomorphism is one of the very few classical problems in NP of unsettled complexity status. Th...
AbstractWe show that Graph Isomorphism is in the complexity class SPP, and hence it is in ⊕P (in fac...
We show that Graph Isomorphism is in the complexity class SPP, and hence it is in ⊕P (in fact, it is...
AbstractWe present eight group-theoretic problems in NP one of which is a reformulation of graph iso...
We study the non-uniform complexity of the Graph Isomorphism (GI) and Graph Automorphism (GA) proble...
Graph isomorphism (GI) is one of the few remaining problems in NP whose complexity status couldn’t b...
AbstractIt is shown that the graph isomorphism problem is located in level L2p of the low hierarchy ...
In this paper we study some classical complexity-theoretic questions regarding Group Isomorphism (Gp...
In this paper I propose a polynomial time algorithm for the Graph Isomorphism problem, which always...
A recent result has shown that the graph isomorphism problem can be solved in quasi-polynomial time,...
AbstractAn open question is the computational complexity of recognizing when two graphs are isomorph...
AbstractDerandomization techniques are used to show that at least one of the following holds regardi...
AbstractWe investigate the computational complexity of the following restricted variant of Subgraph ...
Derandomization techniques are used to show that at least one of the following holds regarding the s...
We study the computational power of deciding whether a given truth-table can be described by a circu...
Graph Isomorphism is one of the very few classical problems in NP of unsettled complexity status. Th...