Arrow Research search

Author name cluster

Gábor Ivanyos

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers
2 author rows

Possible papers

7

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.

Details

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).

Details

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 .

Details