The Experts below are selected from a list of 174 Experts worldwide ranked by ideXlab platform
Youming Qiao - One of the best experts on this subject based on the ideXlab platform.
-
on p Group Isomorphism search to decision counting to decision and nilpotency class reductions via tensors
36th Computational Complexity Conference (CCC 2021), 2021Co-Authors: Joshua A Grochow, Youming QiaoAbstract:In this paper we study some classical complexity-theoretic questions regarding Group Isomorphism (GpI). We focus on p-Groups (Groups of prime power order) with odd p, which are believed to be a bottleneck case for GpI, and work in the model of matrix Groups over finite fields. Our main results are as follows. - Although search-to-decision and counting-to-decision reductions have been known for over four decades for Graph Isomorphism (GI), they had remained open for GpI, explicitly asked by Arvind & Toran (Bull. EATCS, 2005). Extending methods from Tensor Isomorphism (Grochow & Qiao, ITCS 2021), we show moderately exponential-time such reductions within p-Groups of class 2 and exponent p. - Despite the widely held belief that p-Groups of class 2 and exponent p are the hardest cases of GpI, there was no reduction to these Groups from any larger class of Groups. Again using methods from Tensor Isomorphism (ibid.), we show the first such reduction, namely from Isomorphism testing of p-Groups of "small" class and exponent p to those of class two and exponent p. For the first results, our main innovation is to develop linear-algebraic analogues of classical graph coloring gadgets, a key technique in studying the structural complexity of GI. Unlike the graph coloring gadgets, which support restricting to various subGroups of the symmetric Group, the problems we study require restricting to various subGroups of the general linear Group, which entails significantly different and more complicated gadgets. The analysis of one of our gadgets relies on a classical result from Group theory regarding random generation of classical Groups (Kantor & Lubotzky, Geom. Dedicata, 1990). For the nilpotency class reduction, we combine a runtime analysis of the Lazard Correspondence with Tensor Isomorphism-completeness results (Grochow & Qiao, ibid.).
-
incorporating weisfeiler leman into algorithms for Group Isomorphism
arXiv: Computational Complexity, 2019Co-Authors: Peter A Brooksbank, Youming Qiao, Joshua A Grochow, James B WilsonAbstract:In this paper we combine many of the standard and more recent algebraic techniques for testing Isomorphism of finite Groups (GpI) with combinatorial techniques that have typically been applied to Graph Isomorphism. In particular, we show how to combine several state-of-the-art GpI algorithms for specific Group classes into an algorithm for general GpI, namely: composition series Isomorphism (Rosenbaum-Wagner, Theoret. Comp. Sci., 2015; Luks, 2015), recursively-refineable filters (Wilson, J. Group Theory, 2013), and low-genus GpI (Brooksbank-Maglione-Wilson, J. Algebra, 2017). Recursively-refineable filters -- a generalization of subGroup series -- form the skeleton of this framework, and we refine our filter by building a hypergraph encoding low-genus quotients, to which we then apply a hypergraph variant of the k-dimensional Weisfeiler-Leman technique. Our technique is flexible enough to readily incorporate additional hypergraph invariants or additional characteristic subGroups.
-
algorithms based on algebras and their applications to Isomorphism of polynomials with one secret Group Isomorphism and polynomial identity testing
SIAM Journal on Computing, 2019Co-Authors: Gabor Ivanyos, Youming QiaoAbstract:We consider two basic algorithmic problems concerning tuples of (skew-)symmetric matrices. The first problem asks us to decide, given two tuples of (skew-)symmetric matrices $(B_1, \dots, B_m)$ and...
-
algorithms based on algebras and their applications to Isomorphism of polynomials with one secret Group Isomorphism and polynomial identity testing
Symposium on Discrete Algorithms, 2018Co-Authors: Gabor Ivanyos, Youming QiaoAbstract:We consider two basic algorithmic problems concerning tuples of (skew-)symmetric matrices. The first problem asks to decide, given two tuples of (skew-)symmetric matrices (B1, ..., Bm) and (C1, ..., Cm), whether there exists an invertible matrix A such that for every i ∈ {1, ..., m}, AtBiA = Ci. We show that this problem can be solved in randomized polynomial time over finite fields of odd size, the reals, and the complex numbers. The second problem asks to decide, given a tuple of square matrices (B1, ..., Bm), whether there exist invertible matrices A and D, such that for every i ∈ {1, ..., m}, ABiD is (skew-)symmetric. We show that this problem can be solved in deterministic polynomial time over fields of characteristic not 2. For both problems we exploit the structure of the underlying *-algebras (algebras with an involutive anti-automorphism), and utilize results and methods from the module Isomorphism problem. Applications of our results range from multivariate cryptography, Group Isomorphism, to polynomial identity testing. Specifically, these results imply efficient algorithms for the following problems. (1) Test Isomorphism of quadratic forms with one secret over a finite field of odd size. This problem belongs to a family of problems that serves as the security basis of certain authentication schemes proposed by Patarin (Eurocrypt 1996). (2) Test Isomorphism of p-Groups of class 2 and exponent p (p odd) with order pe in time polynomial in the Group order, when the commutator subGroup is of order [EQUATION]. (3) Deterministically reveal two families of singularity witnesses caused by the skew-symmetric structure. This represents a natural next step for the polynomial identity testing problem, in the direction set up by the recent resolution of the non-commutative rank problem (Garg-Gurvits-Oliveira-Wigderson, FOCS 2016; Ivanyos-Qiao-Subrahmanyam, ITCS 2017).
-
linear algebraic analogues of the graph Isomorphism problem and the erdős renyi model
Foundations of Computer Science, 2017Co-Authors: Youming QiaoAbstract:A classical difficult Isomorphism testing problem is to test Isomorphism of p-Groups of class 2 and exponent p in time polynomial in the Group order. It is known that this problem can be reduced to solving the alternating matrix space isometry problem over a finite field in time polynomial in the underlying vector space size. We propose a venue of attack for the latter problem by viewing it as a linear algebraic analogue of the graph Isomorphism problem. This viewpointleads us to explore the possibility of transferring techniques for graph Isomorphism to this long-believed bottleneck case of Group Isomorphism.In 1970s, Babai, Erdős, and Selkow presented the first average-case efficient graph Isomorphism testing algorithm (SIAM J Computing, 1980). Inspired by that algorithm, we devise an average-case efficient algorithm for the alternating matrix space isometry problem over a key range of parameters, in a random model of alternating matrix spaces in vein of the Erd∝os-R´enyi model of random graphs. For this, we develop a linear algebraic analogue of the classical individualisation technique, a technique belonging to a set of combinatorial techniques that has been critical for the progress on the worst-case time complexity for graph Isomorphism, but was missing in the Group Isomorphism context. This algorithm also enables us to improve Higmans 57-year-old lower bound on the number of p-Groups (Proc. of the LMS, 1960). We finally show that Luks dynamic programming technique for graph Isomorphism (STOC 1999) can be adapted to slightly improve the worst-case time complexity of the alternating matrix space isometry problem in a certain range of parameters.Most notable progress on the worst-case time complexity of graph Isomorphism, including Babais recent breakthrough (STOC 2016) and Babai and Luks previous record (STOC 1983), has relied on both Group theoretic and combinatorial techniques. By developing a linear algebraic analogue of the individualisation technique and demonstrating its usefulness in the average-case setting, the main result opens up the possibility of adapting that strategy for graph Isomorphism to this hard instance of Group Isomorphism. The linear algebraic Erdős-Rényi model is of independent interest and may deserve further study.
Jacobo Toran - One of the best experts on this subject based on the ideXlab platform.
-
graph Isomorphism is not ac0 reducible to Group Isomorphism
ACM Transactions on Computation Theory, 2013Co-Authors: Arkadev Chattopadhyay, Jacobo Toran, Fabian WagnerAbstract:We give a new upper bound for the Group and QuasiGroup Isomorphism problems when the input structures are given explicitly by multiplication tables. We show that these problems can be computed by polynomial size nondeterministic circuits of unbounded fan-in with O(log log n) depth and O(log2n) nondeterministic bits, where n is the number of Group elements. This improves the existing upper bound for the problems. In the previous bound the circuits have bounded fan-in but depth O(log2n) and also O(log2n) nondeterministic bits. We then prove that the kind of circuits from our upper bound cannot compute the Parity function. Since Parity is AC0-reducible to Graph Isomorphism, this implies that Graph Isomorphism is strictly harder than Group or QuasiGroup Isomorphism under the ordering defined by AC0 reductions. We extend this result to the stronger ACC0[p] reduction and its randomized version.
-
solvable Group Isomorphism is almost in np conp
ACM Transactions on Computation Theory, 2011Co-Authors: Vikraman Arvind, Jacobo ToranAbstract:The Group Isomorphism problem consists in deciding whether two input Groups G1 and G2 given by their multiplication tables are isomorphic. We first give a 2-round Arthur-Merlin protocol for the Group NonIsomorphism problem such that on input Groups (G1, G2) of size n, Arthur uses O(log6n) random bits and Merlin uses O(log2n) nondeterministic bits. We derandomize this protocol for the case of solvable Groups showing the following two results:(a) We give a uniform NP machine for solvable Group NonIsomorphism, that works correctly on all but 2logO(1)(n) inputs of any length n. Furthermore, this NP machine is always correct when the input Groups are nonisomorphic. The NP machine is obtained by an unconditional derandomization of the aforesaid AM protocol.(b) Under the assumption that EXP \not\subseteq i.o--PSPACE we get a complete derandomization of the aforesaid AM protocol. Thus, EXP \not\subseteq i.o--PSPACE implies that Group Isomorphism for solvable Groups is in NP ∩ coNP.
-
graph Isomorphism is not ac 0 reducible to Group Isomorphism
Foundations of Software Technology and Theoretical Computer Science, 2010Co-Authors: Arkadev Chattopadhyay, Jacobo Toran, Fabian WagnerAbstract:We give a new upper bound for the Group and QuasiGroup Isomorphism problems when the input structures are given explicitly by multiplication tables. We show that these problems can be computed by polynomial size nondeterministic circuits of unbounded fan-in with $O(\log\log n)$ depth and $O(\log^2 n)$ nondeterministic bits, where $n$ is the number of Group elements. This improves the existing upper bound from \cite{Wolf 94} for the problems. In the previous upper bound the circuits have bounded fan-in but depth $O(\log^2 n)$ and also $O(\log^2 n)$ nondeterministic bits. We then prove that the kind of circuits from our upper bound cannot compute the Parity function. Since Parity is AC0 reducible to Graph Isomorphism, this implies that Graph Isomorphism is strictly harder than Group or QuasiGroup Isomorphism under the ordering defined by AC0 reductions.
-
solvable Group Isomorphism is almost in np spl cap conp
Conference on Computational Complexity, 2004Co-Authors: Vikraman Arvind, Jacobo ToranAbstract:The Group Isomorphism problem consists in deciding whether two input Groups G/sup 1/ and G/sup 2/ given by their multiplication tables are isomorphic. We first give a 2-round Arthur-Merlin protocol for the Group non-Isomorphism problem such that on input Groups (G/sup 1/, G/sup 2/) of size n, Arthur uses O(log/sup 6/ n) random bits and Merlin uses O(log/sup 2/ n) nondeterministic bits. We derandomize this protocol for the case of solvable Groups showing the following two results: (a) We give a uniform NP machine for solvable Group non-Isomorphism, that works correctly on all but 2/sup polylog(n)/ inputs of any length n. Furthermore, this NP machine is always correct when the input Groups are nonisomorphic. The NP machine is obtained by an unconditional derandomization of the AM protocol. (b) Under the assumption that EXP /spl nsube/ i.o.PSPACE we get a complete derandomization of the above AM protocol. Thus, EXP /spl nsube/ i.o.PSPACE implies that Group Isomorphism for solvable Groups is in NP /spl cap/ coNP.
-
solvable Group Isomorphism is almost in np conp
Conference on Computational Complexity, 2004Co-Authors: Vikraman Arvind, Jacobo ToranAbstract:The Group Isomorphism problem consists in decidingwhether two input Groups G_1 and G_2 givenby their multiplication tables are isomorphic. Wefirst give a 2-round Arthur-Merlin protocol for theGroup Non-Isomorphism problem such that on inputGroups (G_1,G_2) of size n, Arthur uses O(log^6 n)random bits and Merlin uses O(log^2 n) nondeterministicbits. We derandomize this protocol for thecase of solvable Groups showing the following tworesults:(a) We give a uniform NP machine for solvableGroup Non-Isomorphism, that works correctlyon all but 2^polylog(n) inputs of any length n.Furthermore, this NP machine is always correctwhen the input Groups are nonisomorphic.The NP machine is obtained by an unconditionalderandomization of the AM protocol.(b) Under the assumption that EXP ? i.o.PSPACE we get a complete derandomization of the above AM protocol. Thus,EXP ? i.o.PSPACE implies that Group Isomorphismfor solvable Groups is in NP ? coNP.
James B Wilson - One of the best experts on this subject based on the ideXlab platform.
-
Group Isomorphism is nearly linear time for most orders
arXiv: Computational Complexity, 2020Co-Authors: Heiko Dietrich, James B WilsonAbstract:We show that there is a dense set $\Upsilon\subseteq \mathbb{N}$ of Group orders and a constant $c$ such that for every $n\in \Upsilon$ we can decide in time $O(n^2(\log n)^c)$ whether two $n\times n$ multiplication tables describe isomorphic Groups of order $n$. This improves significantly over the general $n^{O(\log n)}$-time complexity and shows that Group Isomorphism can be tested efficiently for almost all Group orders $n$. We also show that in time $O(n^2 (\log n)^d)$ it can be decided whether an $n\times n$ multiplication table describes a Group; this improves over the known $O(n^3)$ complexity.
-
Group Isomorphism is nearly linear time for most orders
arXiv: Computational Complexity, 2020Co-Authors: Heiko Dietrich, James B WilsonAbstract:We show that there is a dense set $\ourset\subseteq \mathbb{N}$ of Group orders and a constant $c$ such that for every $n\in \ourset$ we can decide in time $O(n^2(\log n)^c)$ whether two $n\times n$ multiplication tables describe isomorphic Groups of order $n$. This improves significantly over the general $n^{O(\log n)}$-time complexity and shows that Group Isomorphism can be tested efficiently for almost all Group orders $n$. We also show that in time $O(n^2 (\log n)^c)$ it can be decided whether an $n\times n$ multiplication table describes a Group; this improves over the known $O(n^3)$ complexity. Our complexities are calculated for a deterministic multi-tape Turing machine model. We give the implications to a RAM model in the promise hierarchy as well.
-
incorporating weisfeiler leman into algorithms for Group Isomorphism
arXiv: Computational Complexity, 2019Co-Authors: Peter A Brooksbank, Youming Qiao, Joshua A Grochow, James B WilsonAbstract:In this paper we combine many of the standard and more recent algebraic techniques for testing Isomorphism of finite Groups (GpI) with combinatorial techniques that have typically been applied to Graph Isomorphism. In particular, we show how to combine several state-of-the-art GpI algorithms for specific Group classes into an algorithm for general GpI, namely: composition series Isomorphism (Rosenbaum-Wagner, Theoret. Comp. Sci., 2015; Luks, 2015), recursively-refineable filters (Wilson, J. Group Theory, 2013), and low-genus GpI (Brooksbank-Maglione-Wilson, J. Algebra, 2017). Recursively-refineable filters -- a generalization of subGroup series -- form the skeleton of this framework, and we refine our filter by building a hypergraph encoding low-genus quotients, to which we then apply a hypergraph variant of the k-dimensional Weisfeiler-Leman technique. Our technique is flexible enough to readily incorporate additional hypergraph invariants or additional characteristic subGroups.
Francois Le Gall - One of the best experts on this subject based on the ideXlab platform.
-
on the Group and color Isomorphism problems
arXiv: Computational Complexity, 2016Co-Authors: Francois Le Gall, David J RosenbaumAbstract:In this paper, we prove results on the relationship between the complexity of the Group and color Isomorphism problems. The difficulty of color Isomorphism problems is known to be closely linked to the the composition factors of the permutation Group involved. Previous works are primarily concerned with applying color Isomorphism to bou nded degree graph Isomorphism, and have therefore focused on the alternating composit ion factors, since those are the bottleneck in the case of graph Isomorphism. We consider the color Isomorphism problem with composition factors restricted to those other than the alternating Group, show that Group Isomorphism reduces in n^(O(log log n)) time to this problem, and, conversely, that a special case of this color Isomorphism problem reduces to a slight generalization of Group Isomorphism. We then sharpen our results by identifying the projective special linear Group as the main obstacle to faster algorithms for Group Isomorphism and prove that the aforementioned reduc tion from Group Isomorphism to color Isomorphism in fact produces only cyclic and projective special linear factors. Our results demonstrate that, just as the alternatin g Group was a barrier to faster algorithms for graph Isomorphism for three decades, the projective special linear Group is an obstacle to faster algorithms for Group Isomorphism.
-
an efficient quantum algorithm for some instances of the Group Isomorphism problem
Symposium on Theoretical Aspects of Computer Science, 2010Co-Authors: Francois Le GallAbstract:In this paper we consider the problem of testing whether two finite Groups are isomorphic. Whereas the case where both Groups are abelian is well understood and can be solved efficiently, very little is known about the complexity of Isomorphism testing for nonabelian Groups. Le Gall has constructed an efficient classical algorithm for a class of Groups corresponding to one of the most natural ways of constructing nonabelian Groups from abelian Groups: the Groups that are extensions of an abelian Group $A$ by a cyclic Group $\Int_m$ with the order of $A$ coprime with $m$. More precisely, the running time of that algorithm is almost linear in the order of the input Groups. In this paper we present a \emph{quantum} algorithm solving the same problem in time polynomial in the \emph{logarithm} of the order of the input Groups. This algorithm works in the black-box setting and is the first quantum algorithm solving instances of the nonabelian Group Isomorphism problem exponentially faster than the best known classical algorithms.
-
efficient Isomorphism testing for a class of Group extensions
Symposium on Theoretical Aspects of Computer Science, 2009Co-Authors: Francois Le GallAbstract:The Group Isomorphism problem asks whether two given Groups are isomorphic or not. Whereas the case where both Groups are abelian is well understood and can be solved efficiently, very little is known about the complexity of Isomorphism testing for nonabelian Groups. In this paper we study this problem for a class of Groups corresponding to one of the simplest ways of constructing nonabelian Groups from abelian Groups: the Groups that are extensions of an abelian Group $A$ by a cyclic Group $\mathbb{Z}_m$. We present an efficient algorithm solving the Group Isomorphism problem for all the Groups of this class such that the order of $A$ is coprime with $m$. More precisely, our algorithm runs in time almost linear in the orders of the input Groups and works in the general setting where the Groups are given as black-boxes.
-
efficient Isomorphism testing for a class of Group extensions
arXiv: Data Structures and Algorithms, 2008Co-Authors: Francois Le GallAbstract:The Group Isomorphism problem asks whether two given Groups are isomorphic or not. Whereas the case where both Groups are abelian is well understood and can be solved efficiently, very little is known about the complexity of Isomorphism testing for nonabelian Groups. In this paper we study this problem for a class of Groups corresponding to one of the simplest ways of constructing nonabelian Groups from abelian Groups: the Groups that are extensions of an abelian Group A by a cyclic Group of order m. We present an efficient algorithm solving the Group Isomorphism problem for all the Groups of this class such that the order of A is coprime with m. More precisely, our algorithm runs in time almost linear in the orders of the input Groups and works in the general setting where the Groups are given as black-boxes.
Vikraman Arvind - One of the best experts on this subject based on the ideXlab platform.
-
solvable Group Isomorphism is almost in np conp
ACM Transactions on Computation Theory, 2011Co-Authors: Vikraman Arvind, Jacobo ToranAbstract:The Group Isomorphism problem consists in deciding whether two input Groups G1 and G2 given by their multiplication tables are isomorphic. We first give a 2-round Arthur-Merlin protocol for the Group NonIsomorphism problem such that on input Groups (G1, G2) of size n, Arthur uses O(log6n) random bits and Merlin uses O(log2n) nondeterministic bits. We derandomize this protocol for the case of solvable Groups showing the following two results:(a) We give a uniform NP machine for solvable Group NonIsomorphism, that works correctly on all but 2logO(1)(n) inputs of any length n. Furthermore, this NP machine is always correct when the input Groups are nonisomorphic. The NP machine is obtained by an unconditional derandomization of the aforesaid AM protocol.(b) Under the assumption that EXP \not\subseteq i.o--PSPACE we get a complete derandomization of the aforesaid AM protocol. Thus, EXP \not\subseteq i.o--PSPACE implies that Group Isomorphism for solvable Groups is in NP ∩ coNP.
-
solvable Group Isomorphism is almost in np spl cap conp
Conference on Computational Complexity, 2004Co-Authors: Vikraman Arvind, Jacobo ToranAbstract:The Group Isomorphism problem consists in deciding whether two input Groups G/sup 1/ and G/sup 2/ given by their multiplication tables are isomorphic. We first give a 2-round Arthur-Merlin protocol for the Group non-Isomorphism problem such that on input Groups (G/sup 1/, G/sup 2/) of size n, Arthur uses O(log/sup 6/ n) random bits and Merlin uses O(log/sup 2/ n) nondeterministic bits. We derandomize this protocol for the case of solvable Groups showing the following two results: (a) We give a uniform NP machine for solvable Group non-Isomorphism, that works correctly on all but 2/sup polylog(n)/ inputs of any length n. Furthermore, this NP machine is always correct when the input Groups are nonisomorphic. The NP machine is obtained by an unconditional derandomization of the AM protocol. (b) Under the assumption that EXP /spl nsube/ i.o.PSPACE we get a complete derandomization of the above AM protocol. Thus, EXP /spl nsube/ i.o.PSPACE implies that Group Isomorphism for solvable Groups is in NP /spl cap/ coNP.
-
solvable Group Isomorphism is almost in np conp
Conference on Computational Complexity, 2004Co-Authors: Vikraman Arvind, Jacobo ToranAbstract:The Group Isomorphism problem consists in decidingwhether two input Groups G_1 and G_2 givenby their multiplication tables are isomorphic. Wefirst give a 2-round Arthur-Merlin protocol for theGroup Non-Isomorphism problem such that on inputGroups (G_1,G_2) of size n, Arthur uses O(log^6 n)random bits and Merlin uses O(log^2 n) nondeterministicbits. We derandomize this protocol for thecase of solvable Groups showing the following tworesults:(a) We give a uniform NP machine for solvableGroup Non-Isomorphism, that works correctlyon all but 2^polylog(n) inputs of any length n.Furthermore, this NP machine is always correctwhen the input Groups are nonisomorphic.The NP machine is obtained by an unconditionalderandomization of the AM protocol.(b) Under the assumption that EXP ? i.o.PSPACE we get a complete derandomization of the above AM protocol. Thus,EXP ? i.o.PSPACE implies that Group Isomorphismfor solvable Groups is in NP ? coNP.
