Main Publications by Subjects

In the following, I organise (most of) my works into some categories, to illustrate my research directions by topics.

Tensor Isomorphism: complexity, algorithms, and cryptography

Complexity

The following papers are in the main Tensor Isomorphism series. 

1. On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor Isomorphism-completeness

   • Joshua A. Grochow, Youming Qiao

   • SIAM Journal on Computing, 52(2): 568-617 (2023). [DOI]

   • ITCS 2021. [arXiv]

2. On p-Group Isomorphism: search-to-decision, counting-to-decision, and nilpotency class reductions via tensors

   • Joshua A. Grochow, Youming Qiao

   • ACM Transactions on Computation Theory, 16(1): 2:1-2:39 (2024). [DOI]

   • CCC 2021. [DOI]

   • Note: this is the second paper in the Tensor Isomorphism series.

3. On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups

   • Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, Chuanqi Zhang. 

   • ITCS 2024. [DOI, arXiv]

   • Also presented at TQC 2024. [link]

4. On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications

   • Joshua A. Grochow, Youming Qiao

   • To appear in STOC 2025. [arXiv]

5. On the complexity of isomorphism problems for tensors, groups, and polynomials V: over commutative rings

   • Joshua A. Grochow, Youming Qiao, Katherine E. Stange, Xiaorui Sun

   • To appear in STOC 2025.

The following papers are extensions to the main series. 

1. Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms

   • Joshua A. Grochow, Youming Qiao, Gang Tang

   • journal of Groups, Complexity, Cryptology, 14:1 (2022). [link]

   • STACS 2021. [arXiv]

Algorithms

The following papers are for algorithms for tensor isomorphism and its variations.

1. [Worst-case algorithms] Faster isomorphism testing of p-groups of Frattini class 2

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

   • FOCS 2024. [link]

2. [Worst-case algorithms] 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

   • SIAM Journal on Computing, 48(3): 926-963 (2019). [DOI]

   • SODA 2018. [arXiv]

3. [Average-case algorithms] Linear algebraic analogues of the graph isomorphism problem and the Erdős-Rényi model

   • Yinan Li, Youming Qiao

   • FOCS 2017. [arXiv]

   • The arXiv version 2 contains a correction to the implications to group enumeration. The desired group enumeration result was recently achieved here.

4. [Average-case algorithms] Improved algorithms for alternating matrix space isometry: from theory to practice

   • Peter A. Brooksbank, Yinan Li, Youming Qiao, James B. Wilson

   • ESA 2020. 

5. [Heuristic algorithms] Algorithms for matrix code and alternating trilinear form equivalences via new isomorphism invariants

   • Anand Kumar Narayanan, Youming Qiao, Gang Tang

   • Eurocrypt 2024. [eprint]

   • Also presented at the fifth NIST PQC Standardization Conference. [link]

Cryptography

The following papers are for tensor isomorphism in cryptography. 

1. General linear group action on tensors: a candidate for post-quantum cryptography

   • Zhengfeng Ji, Youming Qiao, Fang Song, Aaram Yun

   • TCC 2019. [arXiv] 

   • Also accepted as a talk in QIP 2020.

2. Practical post-quantum signature schemes from isomorphism problems of trilinear forms

   • (*) Gang Tang, Dung Hoang Duong, Antoine Joux, Thomas Plantard, Youming Qiao, Willy Susilo

   • Eurocrypt 2022. [Cryptology ePrint Archive]

3. On digital signatures based on group actions: QROM security and ring signatures

   • Markus Bläser, Zhili Chen, Dung Hoang Duong, Antoine Joux, Ngoc Tuong Nguyen, Thomas Plantard, Youming Qiao, Willy Susilo, Gang Tang

   • PQCrypto 2024. [eprint]

4. Algorithms for matrix code and alternating trilinear form equivalences via new isomorphism invariants

   • Anand Kumar Narayanan, Youming Qiao, Gang Tang

   • Eurocrypt 2024. [eprint]

   • Also presented at the fifth NIST PQC Standardization Conference. [link]

Polynomial identity testing and algebraic complexity

The following papers settle the non-commutative rank problem for symbolic matrices (the other two solutions are here and here), and the related orbit closure intersection problems (the other two solutions are here and here). 

1. Non-commutative Edmonds' problem and matrix semi-invariants

   • Gábor Ivanyos, Youming Qiao, K. V. Subrahmanyam

   • Computational Complexity, 26(3): 717-763 (2017). [arXiv] [DOI]

2. Constructive non-commutative rank is in deterministic polynomial time

   • Gábor Ivanyos, Youming Qiao, K. V. Subrahmanyam

   • Computational Complexity, 27(4): 561-593 (2018). [DOI]

   • ITCS 2017. [arXiv]

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

   • Gábor Ivanyos, Youming Qiao

   • SODA 2023. [DOI]

4. Generalized Wong sequences and their applications to Edmonds’ problems

   • Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha

   • Journal of Computer and System Sciences 81(7): 1373-1386 (2015).

   • STACS 2014. [arXiv], [ECCC] 

   • This is the paper that introduced "Wong sequences", a linear algebraic analogue of alternating paths, that play a key role in our approach of settling non-commutative ranks.

After settling the non-commutative rank problem, we explored some singular matrix spaces without shrunk subspaces. 

1. Symbolic determinant identity testing and non-commutative ranks of matrix Lie algebras

   • Gábor Ivanyos, Tushant Mittal, Youming Qiao

   • ITCS 2022. [arXiv]

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

   • SIAM Journal on Computing, 48(3): 926-963 (2019). [DOI]

   • SODA 2018. [arXiv]

3. Connections between graphs and matrix spaces

   • Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang. 

   • Israel Journal of Mathematics, 256 (2), 513-580 (2023). [arXiv]

Before working on the non-commutative rank problem, I have the following papers on algebraic complexity.

1. Sparse multivariate polynomial interpolation in the basis of Schubert polynomials

   • Priyanka Mukhopadhyay, Youming Qiao

   • Computational Complexity, 26(4): 881–909 (2017). [arXiv] [DOI]

2. Boundaries of VP and VNP

   • Joshua A. Grochow, Ketan D. Mulmuley, Youming Qiao

   • ICALP 2016. [arXiv]

3. Deterministic black-box identity testing π-ordered algebraic branching programs

   • Maurice Jansen, Youming Qiao, Jayalal M.N. Sarma

   • FSTTCS 2010. [arXiv], [ECCC]

4. Random arithmetic formulas can be reconstructed efficiently 

   • Ankit Gupta, Neeraj Kayal, Youming Qiao

   • Computational Complexity 23(2): 207-303 (2014).

   • CCC 2013. [ECCC]

5. Determinantal complexities and field extensions

   • Youming Qiao, Xiaoming Sun, Nengkun Yu

   • ISAAC 2013. [PDF]

Group isomorphism

Before working on tensor isomorphism (which can be cast as a special case of group isomorphism), I worked on group isomorphism. 

1. Algorithms for group isomorphism via group extensions and cohomology 

   • Joshua A. Grochow, Youming Qiao

   • SIAM Journal on Computing, 46(4): 1153-1216 (2017). [Open access]

     1. (Special thanks go to the Santa Fe Institute for sponsoring the open access of this article.)

   • CCC 2014.  [arXiv]

   • This paper may be viewed as a summary of my works on group isomorphism before 2015. After this paper, my research on isomorphism problem turned to tensor isomorphism and related problems.

2. Polynomial-time isomorphism test of groups that are tame extensions - (Extended Abstract)

   • Joshua A. Grochow, Youming Qiao

   • ISAAC 2015. [arXiv]

3. On isomorphism testing of groups with normal Hall subgroups 

   • Youming Qiao, Jayalal M.N. Sarma, Bangsheng Tang

   • Journal of Computer Science and Technology 27(4): 687-701 (2012)

   • STACS 2011. [PDF] 

4. Polynomial-time isomorphism test for groups with no abelian normal subgroups

   • László Babai, Paolo Codenotti, Youming Qiao

   • ICALP 2012. [PDF] 

5. Polynomial-time isomorphism test for groups with abelian Sylow towers

   • László Babai, Youming Qiao

   • STACS 2012. [PDF]

6. Code equivalence and group isomorphism

   • László Babai, Paolo Codenotti, Joshua A. Grochow, Youming Qiao

   • SODA 2011. [PDF]

Quantum information and computation

My works on quantum information and computation include some papers on complexity and with quantum implications.

1. On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor Isomorphism-completeness

   • Joshua A. Grochow, Youming Qiao

   • SIAM Journal on Computing, 52(2): 568-617 (2023). [DOI]

   • ITCS 2021. [arXiv]

2. On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups

   • Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, Chuanqi Zhang. 

   • ITCS 2024. [DOI, arXiv]

   • Also presented at TQC 2024. [link]

3. On the complexity of isomorphism problems for tensors, groups, and polynomials V: over commutative rings

   • Joshua A. Grochow, Youming Qiao, Katherine E. Stange, Xiaorui Sun

   • STOC 2025. [DOI]

4. Tripartite-to-bipartite entanglement transformation by stochastic local operations and classical communication and the structure of matrix spaces

   • (*) Yinan Li, Youming Qiao, Xin Wang, Runyao Duan

   • Communications in Mathematical Physics, 358(2): 791-814 (2018). [arXiv] [DOI]

5. An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group

   • Thomas Decker, Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha

   • MFCS 2014. [arXiv] 

6. Local equivalence of multipartite entanglement

1. • Youming Qiao, Xiaoming Sun, Nengkun Yu

   • IEEE Journal of Selected Areas in Communications, 38(3): 568-574 (2020). [arXiv]

Combinatorics and group theory

My works on groups and combinatorics are usually motivated by questions from theoretical computer science. 

1. On average orders of automorphism groups of bilinear maps over finite fields

   • Markus Bläser, Yinan Li, Youming Qiao, Alexander Rogovskyy. 2025. [arXiv]

2. A q-analogue of graph independence polynomials with a group-theoretic interpretation

   • Youming Qiao. 2024. [arXiv]

3. On linear-algebraic notions of expansion

   • Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang

   • Theory of Computing, 21(1):1-28 (2025). [ToC], [arXiv]

4. Connections between graphs and matrix spaces

   • Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang. 

   • Israel Journal of Mathematics, 256 (2), 513-580 (2023). [arXiv]

5. Turán and Ramsey problems for alternating multilinear maps

   • Youming Qiao. 

   • Discrete Analysis, 2023:12 (2023). [arXiv]

6. Enumerating alternating matrix spaces over finite fields with explicit coordinates

   • Youming Qiao

   • Discrete Mathematics, 344(11): 112580 (2021). [arXiv]

7. On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions

   • Xiaoyu He, Youming Qiao

   • European Journal of Combinatorics, 98: 103404 (2021). [arXiv]

8. From independent sets and vertex colorings to isotropic spaces and isotropic decompositions

   • Xiaohui Bei, Shiteng Chen, Ji Guan, Youming Qiao, Xiaoming Sun

   • SIAM Journal on Computing, 50(3), 924–971 (2021). [DOI]

   • ITCS 2020. [arXiv]

9. Group-theoretic generalisations of vertex and edge connectivities

   • Yinan Li, Youming Qiao

   • Proceedings of the American Mathematical Society, 148: 4679-4693 (2020). [DOI] [arXiv]

10. An improved diameter bound for finite simple groups of Lie type

    • Zoltán Halasi, Attila Maróti, László Pyber, Youming Qiao

    • Bulletin of the London Mathematical Society, 51(4): 645-657 (2019). [DOI] [arXiv]

11. On rank-critical matrix spaces

    • Yinan Li, Youming Qiao

    • Differential Geometry and its Applications, 55: 68-77 (2017). [arXiv] [DOI]