Youming Qiao
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Youming Qiao has a total of 83 co-authors. Here are the top co-authors by number of shared publications:
- Gábor Ivanyos
HUN-REN Institute for Computer Science and Control Budapest Hungary
15 shared publications - Joshua A. Grochow
University of Colorado Boulder
7 shared publications Raghav Kulkarni
5 shared publicationsJoshua A. Grochow
4 shared publications- K. Venkata Subrahmanyam
Chennai Mathematical Institute
4 shared publications - Xiaoming Sun
Institute of Computing Technology
4 shared publications
Latest Publications
- Open Access
- 2 November 2026
- Published by Wiley in Bulletin of the London Mathematical Society
- Vol. 58 (11) , e70539
A q‐analogue of graph independence polynomials with a group‐theoretic interpretation
We define totally‐isotropic space polynomials of alternating matrix spaces over finite fields, by analogy with independence polynomials of graphs. Our main result shows that totally‐isotropic space polynomials of graphical alternating matrix spaces give rise to a natural ‐analogue of graph independence polynomials. For ‐groups of class 2 and exponent , this family of polynomials over fields of order can be naturally interpreted as enumerating their abelian subgroups containing the commutator subgroup according to the orders. With this interpretation, our main result has implications to graphical groups over where is an odd prime, in the same spirit as the results in ( Bull. Lond. Math. Soc ., 2022) by Rossmann, who studied enumerating conjugacy classes of graphical groups over finite fields.
- 2 November 2026
- Published by Wiley in Bulletin of the London Mathematical Society
- Vol. 58 (11) , e70539
Open AccessA q‐analogue of graph independence polynomials with a group‐theoretic interpretation
We define totally‐isotropic space polynomials of alternating matrix spaces over finite fields, by analogy with independence polynomials of graphs. Our main result shows that totally‐isotropic space polynomials of graphical alternating matrix spaces give rise to a natural ‐analogue of graph independence polynomials. For ‐groups of class 2 and exponent , this family of polynomials over fields of order can be naturally interpreted as enumerating their abelian subgroups containing the commutator subgroup according to the orders. With this interpretation, our main result has implications to graphical groups over where is an odd prime, in the same spirit as the results in ( Bull. Lond. Math. Soc ., 2022) by Rossmann, who studied enumerating conjugacy classes of graphical groups over finite fields.
- Open Access
- 22 September 2026
- Published by Springer Nature in computational complexity
- Vol. 35 (2) , 13
On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups
We study the complexity of isomorphism problems for tensors, represented in coordinates by multiway arrays, under natural actions by classical groups such as orthogonal, unitary, and symplectic groups. These problems arise naturally in statistical data analysis and quantum information. We study two types of complexity-theoretic questions. First, for a fixed action type (isomorphism, conjugacy, etc.), we relate the complexity of the isomorphism problem over a classical group to that over the general linear group. Second, for a fixed group type (orthogonal, unitary, or symplectic), we compare the complexity of the isomorphism problems for different actions. Our main results are as follows. First, for orthogonal and symplectic groups acting on 3-way arrays, the isomorphism problems reduce to the corresponding problems over the general linear group. Second, for orthogonal and unitary groups, the isomorphism problems of five natural actions on 3-way arrays are polynomial-time equivalent, and the d -tensor isomorphism problem reduces to the 3-tensor isomorphism problem for any fixed $$d>3$$ . For unitary groups, the preceding result implies that LOCC classification of tripartite quantum states is at least as difficult as LOCC classification of d -partite quantum states for any d . Lastly, we also show that the graph isomorphism problem reduces to the tensor isomorphism problem over orthogonal and unitary groups.- 22 September 2026
- Published by Springer Nature in computational complexity
- Vol. 35 (2) , 13
Open AccessOn the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups
We study the complexity of isomorphism problems for tensors, represented in coordinates by multiway arrays, under natural actions by classical groups such as orthogonal, unitary, and symplectic groups. These problems arise naturally in statistical data analysis and quantum information. We study two types of complexity-theoretic questions. First, for a fixed action type (isomorphism, conjugacy, etc.), we relate the complexity of the isomorphism problem over a classical group to that over the general linear group. Second, for a fixed group type (orthogonal, unitary, or symplectic), we compare the complexity of the isomorphism problems for different actions. Our main results are as follows. First, for orthogonal and symplectic groups acting on 3-way arrays, the isomorphism problems reduce to the corresponding problems over the general linear group. Second, for orthogonal and unitary groups, the isomorphism problems of five natural actions on 3-way arrays are polynomial-time equivalent, and the d -tensor isomorphism problem reduces to the 3-tensor isomorphism problem for any fixed $$d>3$$ . For unitary groups, the preceding result implies that LOCC classification of tripartite quantum states is at least as difficult as LOCC classification of d -partite quantum states for any d . Lastly, we also show that the graph isomorphism problem reduces to the tensor isomorphism problem over orthogonal and unitary groups. - Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 777-784
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials V: Over Commutative Rings
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 777-784
Open AccessOn the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials V: Over Commutative Rings
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 766-776
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials IV: Linear-Length Reductions and Their Applications
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 766-776
Open AccessOn the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials IV: Linear-Length Reductions and Their Applications
- Open Access
On average orders of automorphism groups of bilinear maps over finite fields
Let $\varphi:V\times V\to W$ be a bilinear map of finite vector spaces $V$ and $W$ over a finite field $\mathbb{F}_q$. We present asymptotic bounds on the number of isomorphism classes of bilinear maps under the natural action of $\mathrm{GL}(V)$ and $\mathrm{GL}(W)$, when $\dim(V)$ and $\dim(W)$ are linearly related. As motivations and applications of the results, we present almost tight upper bounds on the number of $p$-groups of Frattini class $2$ as first studied by Higman (Proc. Lond. Math. Soc., 1960). Such bounds lead to answers for some open questions by Blackburn, Neumann, and Venkataraman (Cambridge Tracts in Mathematics, 2007). Further applications include sampling matrix spaces with the trivial automorphism group, and asymptotic bounds on the number of isomorphism classes of finite cube-zero commutative algebras.Open AccessOn average orders of automorphism groups of bilinear maps over finite fields
Let $\varphi:V\times V\to W$ be a bilinear map of finite vector spaces $V$ and $W$ over a finite field $\mathbb{F}_q$. We present asymptotic bounds on the number of isomorphism classes of bilinear maps under the natural action of $\mathrm{GL}(V)$ and $\mathrm{GL}(W)$, when $\dim(V)$ and $\dim(W)$ are linearly related. As motivations and applications of the results, we present almost tight upper bounds on the number of $p$-groups of Frattini class $2$ as first studied by Higman (Proc. Lond. Math. Soc., 1960). Such bounds lead to answers for some open questions by Blackburn, Neumann, and Venkataraman (Cambridge Tracts in Mathematics, 2007). Further applications include sampling matrix spaces with the trivial automorphism group, and asymptotic bounds on the number of isomorphism classes of finite cube-zero commutative algebras. - Open Access
A q-analogue of graph independence polynomials with a group-theoretic interpretation
We define totally-isotropic polynomials of alternating matrix spaces over finite fields, by analogy with independence polynomials of graphs. Our main result shows that totally-isotropic polynomials of graphical alternating matrix spaces give rise to a natural q-analogue of graph independence polynomials. For p-groups of class 2 and exponent p, this family of polynomials over fields of order p can be naturally interpreted as enumerating their abelian subgroups containing the commutator subgroup according to the orders. With this interpretation, our main result has implications to graphical groups over finite fields, in the same spirit as the results in (Bull. Lond. Math. Soc., 2022) by Rossmann, who studied enumerating conjugacy classes of graphical groups over finite fields.
Open AccessA q-analogue of graph independence polynomials with a group-theoretic interpretation
We define totally-isotropic polynomials of alternating matrix spaces over finite fields, by analogy with independence polynomials of graphs. Our main result shows that totally-isotropic polynomials of graphical alternating matrix spaces give rise to a natural q-analogue of graph independence polynomials. For p-groups of class 2 and exponent p, this family of polynomials over fields of order p can be naturally interpreted as enumerating their abelian subgroups containing the commutator subgroup according to the orders. With this interpretation, our main result has implications to graphical groups over finite fields, in the same spirit as the results in (Bull. Lond. Math. Soc., 2022) by Rossmann, who studied enumerating conjugacy classes of graphical groups over finite fields.
- 11 June 2024
- Published by Springer Nature
- p. 227-261
On Digital Signatures Based on Group Actions: QROM Security and Ring Signatures
- 11 June 2024
- Published by Springer Nature
- p. 227-261
On Digital Signatures Based on Group Actions: QROM Security and Ring Signatures
- 1 May 2024
- Published by Springer Nature
- p. 160-187
Algorithms for Matrix Code and Alternating Trilinear Form Equivalences via New Isomorphism Invariants
- 1 May 2024
- Published by Springer Nature
- p. 160-187
Algorithms for Matrix Code and Alternating Trilinear Form Equivalences via New Isomorphism Invariants
- Open Access
- 12 March 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 16 (1) , 1-39
On p -Group Isomorphism: Search-to-Decision, Counting-to-Decision, and Nilpotency Class Reductions via Tensors
In this article, 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 bottleneckcase 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 more than four decades for Graph Isomorphism , they had remained open for GpI , explicitly asked by Arvind and Torán ( EATCS Bull. , 2005). Extending methods from Tensor Isomorphism (TI) (Grochow and 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 TI (ibid.), we show the first such reduction, namely from isomorphismtesting 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 Graph Isomorphism . 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 and Lubotzky, Geom. Dedicata , 1990). For the nilpotency class reduction, we combine a runtime analysis of the Lazard correspondence with TI-completeness results (Grochow and Qiao, ibid.).
- 12 March 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 16 (1) , 1-39
Open AccessOn p -Group Isomorphism: Search-to-Decision, Counting-to-Decision, and Nilpotency Class Reductions via Tensors
In this article, 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 bottleneckcase 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 more than four decades for Graph Isomorphism , they had remained open for GpI , explicitly asked by Arvind and Torán ( EATCS Bull. , 2005). Extending methods from Tensor Isomorphism (TI) (Grochow and 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 TI (ibid.), we show the first such reduction, namely from isomorphismtesting 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 Graph Isomorphism . 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 and Lubotzky, Geom. Dedicata , 1990). For the nilpotency class reduction, we combine a runtime analysis of the Lazard correspondence with TI-completeness results (Grochow and Qiao, ibid.).
- 1 September 2023
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 256 (2) , 513-580
Connections between graphs and matrix spaces
- 1 September 2023
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 256 (2) , 513-580
Connections between graphs and matrix spaces