Gábor Ivanyos

FOCS Conference 2024 Conference Paper

Faster Isomorphism Testing of p-Groups of Frattini Class 2

• Gábor Ivanyos
• Euan J. Mendoza
• Youming Qiao
• Xiaorui Sun
• Chuanqi Zhang

The finite group isomorphism problem asks to decide whether two finite groups of order $N$ are isomorphic. Improving the classical $N^{O(\mathrm{I}\mathrm{o}\mathrm{g}N)}$ -time algorithm for group isomorphism is a long-standing open problem. It is generally regarded that $p$ groups of class 2 and exponent $p$ form a bottleneck case for group isomorphism in general. The recent breakthrough by Sun (STOC '23) presents an $N^{O\left((\log N)^{5 / 6}\right)}$ -time algorithm for this group class. In this paper, we improve Sun's algorithm by presenting an $N^{{\tilde{O}}\left((\log {N})^{1^{1 / 2}}\right)}$ -time algorithm for this group class. We also extend our result to the more general $p$ -groups of Frattini class 2. Our algorithm is obtained by sharpening the key technical ingredients in Sun's algorithm and building connections with other research topics. One intriguing connection is with the maximal and non-commutative ranks of matrix spaces, which have recently received considerable attention in algebraic complexity and computational invariant theory. Results from the theory of Tensor Isomorphism complexity class (Grochow-Qiao, SIAM J. Comput. '23) are utilized to simplify the algorithm and achieve the extension to $p$ -groups of Frattini class 2.

SODA Conference 2023 Conference Paper

On the orbit closure intersection problems for matrix tuples under conjugation and left-right actions

• Gábor Ivanyos
• Youming Qiao

Let G be a linear algebraic group acting on the vector space V. Given v, v ' ∈ V, the orbit closure intersection problem asks to decide if the orbit closures of v and v' under G intersect. Due to connections with polynomial identity testing, the orbit closure intersection problems for the conjugation and left-right actions on matrix tuples received considerable attention in computational complexity and computational invariant theory, as seen in the works of Forbes-Shpilka ( RANDOM 2013), Allen-Zhu-Garg-Li-Oliveira-Wigderson ( STOC 2018), and Derksen-Makam ( Algebra & Number Theory 2020). In this paper, we present new algorithms for the orbit closure problem for the conjugation and left-right actions on matrix tuples. The main novel feature is that in the case of intersecting orbit closures, our algorithm outputs cosets of one-parameter subgroups that drive the matrix tuples to a tuple in the intersection of the orbit closures.

SODA Conference 2018 Conference Paper

Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing

• Gábor Ivanyos
• Youming Qiao

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 ( B 1, …, B m ) and ( C 1, …, C m ), whether there exists an invertible matrix A such that for every i ∊ {1, …, m }, A t B i A = C i. 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 ( B 1, …, B m ), whether there exist invertible matrices A and D, such that for every i ∊ {1, …, m }, AB i D 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 antiautomorphism), 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 p ℓ in time polynomial in the group order, when the commutator subgroup is of order. (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).

TCS Journal 2017 Journal Article

Solving systems of diagonal polynomial equations over finite fields

• Gábor Ivanyos
• Miklos Santha

We present an algorithm to solve a system of diagonal polynomial equations over finite fields when the number of variables is greater than some fixed polynomial of the number of equations whose degree depends only on the degree of the polynomial equations. Our algorithm works in time polynomial in the number of equations and the logarithm of the size of the field, whenever the degree of the polynomial equations is constant. As a consequence we design polynomial time quantum algorithms for two algebraic hidden structure problems: for the hidden subgroup problem in certain semidirect product p-groups of constant nilpotency class, and for the multi-dimensional univariate hidden polynomial graph problem when the degree of the polynomials is constant. 1

STOC Conference 2005 Conference Paper

Efficient testing of groups

• Katalin Friedl
• Gábor Ivanyos
• Miklos Santha

We construct an efficient probabilistic algorithm that, given a finite set with a binary operation, tests if it is an abelian group. The distance used is an analogue of the edit distance for strings. The query complexity of the tester is polylogarithmic in the size of the set. Previous testers used Hamming type distances and had superlinear query complexity. A building block for our construction is a constant query complexity homomorphism tester for functions mapping an given finite group into an arbitrary set equipped with a binary operation.

STOC Conference 2003 Conference Paper

Hidden translation and orbit coset in quantum computing

• Katalin Friedl
• Gábor Ivanyos
• Frédéric Magniez
• Miklos Santha
• Pranab Sen

We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of non-abelian groups including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in Z p n , whenever p is a fixed prime. For the induction step, we introduce the problem Orbit Coset generalizing both Hidden Translation and Hidden Subgroup , and prove a powerful self-reducibility result: Orbit Coset in a finite group G is reducible to Orbit Coset in G/N and subgroups of N , for any solvable normal subgroup N of G .

SODA Conference 1996 Conference Paper

Multiplicative Equations over Commuting Matrices

• László Babai
• Robert Beals
• Jin-Yi Cai
• Gábor Ivanyos
• Eugene M. Luks