Youming Qiao

Email: jimmyqiao86 [at] gmail.com

About Me

I am an associate professor at the Centre for Quantum Software and Information, University of Technology Sydney. 

I work in theoretical computer science. Within this broad area, my main research interests lie in computational complexity theory and algebraic computation. I also have interests in cryptography, quantum information and computation, and group theory.

Short Bio

In 2008, I obtained my B.S. from the Department of Computer Science and Technology at Tsinghua University at Beijing, China. In 2012, I received my Ph.D. from Institute for Interdisciplinary Information Sciences of Tsinghua University. My advisors were Andrew Yao and László Babai. During my PhD studies, I was a visiting student three times with the Theory Group in the Department of Computer Science at the University of Chicago.

After graduation, I was a research fellow at the National University of Singapore, hosted by Miklos Santha from 2012 to 2014. In 2014, I joined the University of Technology Sydney (UTS) in 2014 as a Lecturer and was promoted to Associate Professor in 2021. My research from Jan 2015 to Dec 2017 was supported by a Discovery Early Career Researcher Award from the Australian Research Council. 

From Jan to June 2025, I was a member of the Computer Science and Discrete Mathematics group at Institute for Advanced Study in Princeton, hosted by Avi Wigderson and Irit Dinur. 

For more information, here is my CV (updated on June 9, 2025). 

My students

• My PhD students:

  1. Yinan Li (joint with Prof Runyao Duan): graduated from UTS in 2018, currently an assistant professor at Wuhan University.

  2. Gang Tang: at UTS from 2020 to 2024. Then a postdoc at the University of Birmingham. 

  3. Chuanqi Zhang: at UTS since 2021. 

  4. Euan Mendoza: at UTS since 2025. 

• My master students:

  1. Zhili Chen: at UTS from 2022 to 2023. Then a PhD at National University of Singapore.

• My honours students:

  1. Chris Atchison: at UTS in 2023. Then a software engineer at ThreatDefence.

  2. Euan Mendoza: at UTS from 2023 to 2024. Then a PhD at UTS. 

  3. Antonius Gunawan: at UTS in 2025. 

  4. Linus Kirkwood: at UTS in 2025. 

Publications

In the following, except those marked with *, the authors are ordered alphabetically according to their last names. This follows the tradition of theoretical computer science and mathematics. There are three papers marked with *, and the first authors of these papers were PhD students under my supervision or mentor.

A list with more detailed bibliography information can be found here. 

1. 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]

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

   • Joshua A. Grochow, Youming Qiao

   • STOC 2025. [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. 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]

5. Canonical forms for matrix tuples in polynomial time

   • Youming Qiao, Xiaorui Sun

   • FOCS 2024. [arXiv]

6. 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]

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

8. 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]

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

10. 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]

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

    • Youming Qiao. 

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

12. 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]

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

    • Gábor Ivanyos, Youming Qiao

    • SODA 2023. [DOI]

14. 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]

15. Heterogeneous multi-commodity network flows over time

    • (*) Yifen Li, Xiaohui Bei, Youming Qiao, Dacheng Tao and Zhiya Chen

    • CSR 2022. [Springer]

16. 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]

17. The isomorphism problem for plain groups is in Σ_3^P

    • Heiko Dietrich, Murray Elder, Adam Piggott, Youming Qiao, Armin Weiß

    • STACS 2022. [arXiv]

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

    • Gábor Ivanyos, Tushant Mittal, Youming Qiao

    • ITCS 2022. [arXiv]

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

    • Youming Qiao

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

20. 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]

21. 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]

22. Improved algorithms for alternating matrix space isometry: from theory to practice

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

    • ESA 2020. 

23. Group-theoretic generalisations of vertex and edge connectivities

    • Yinan Li, Youming Qiao

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

24. Local equivalence of multipartite entanglement

    • Youming Qiao, Xiaoming Sun, Nengkun Yu

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

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

26. 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]

27. 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]

28. 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]

29. 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]

30. On the complexity of trial and error for constraint satisfaction problems

    • Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram

    • Journal of Computer and System Sciences 92: 48-64 (2018). [DOI]

    • ICALP 2014. [ECCC] 

31. 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]

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

    • CCC 2014.  [arXiv]

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

    • Priyanka Mukhopadhyay, Youming Qiao

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

33. 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]

34. On rank-critical matrix spaces

    • Yinan Li, Youming Qiao

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

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

36. Networked fairness in cake cutting

    • Xiaohui Bei, Youming Qiao, Shengyu Zhang

    • IJCAI 2017. [arXiv]

37. On the Polynomial Parity Argument complexity of the Combinatorial Nullstellensatz

    • Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, Siyi Yang

    • CCC 2017. [Open Access]

38. 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] 

39. Boundaries of VP and VNP

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

    • ICALP 2016. [arXiv]

40. 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] 

41. On the power of parity queries in boolean decision trees

    • Raghav Kulkarni, Youming Qiao, Xiaoming Sun

    • TAMC 2015. [Link]

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

    • Joshua A. Grochow, Youming Qiao

    • ISAAC 2015. [arXiv]

43. Random arithmetic formulas can be reconstructed efficiently 

    • Ankit Gupta, Neeraj Kayal, Youming Qiao

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

    • CCC 2013. [ECCC]

44. Determinantal complexities and field extensions

    • Youming Qiao, Xiaoming Sun, Nengkun Yu

    • ISAAC 2013. [PDF]

45. Any monotone property of 3-uniform hypergraphs is weakly evasive

    • Raghav Kulkarni, Youming Qiao, Xiaoming Sun

    • Theoretical Computer Science 588: 16-23 (2015). 

    • TAMC 2013. [PDF] 

46. On the security of Goldreich’s one-way function 

    • Andrej Bogdanov, Youming Qiao

    • Computational Complexity 21(1): 83-127 (2012)

    • RANDOM 2009. [PDF]

47. 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] 

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

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

    • ICALP 2012. [PDF] 

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

    • László Babai, Youming Qiao

    • STACS 2012. [PDF]

50. Code equivalence and group isomorphism

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

    • SODA 2011. [PDF]

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

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

    • FSTTCS 2010. [arXiv], [ECCC]

52. Counting method for multiparty computation over non-abelian groups

    • Youming Qiao, Christophe Tartary

    • CANS 2008.

Preprints

• On average orders of automorphism groups of bilinear maps over finite fields

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

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

  • Youming Qiao. 2024. [arXiv]

• Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions

  • Joshua A. Grochow, Youming Qiao. 2019. [arXiv]

  • Parts of this manuscript were published in ITCS 2021 and CCC 2021.

• Incorporating Weisfeiler-Leman into algorithms for group isomorphism

  • Peter A. Brooksbank, Joshua A. Grochow, Yinan Li, Youming Qiao, James B. Wilson. 2019. [arXiv]

  • A part of this manuscript was published in ESA 2020.

• On generating the ring of matrix semi-invariants

  • Gábor Ivanyos, Youming Qiao, K. V. Subrahmanyam. 2015. [arXiv]

• Deterministic black-box identity testing read-once algebraic branching programs 

  • Maurice Jansen, Youming Qiao, Jayalal M.N. Sarma. 2009. [arXiv], [ECCC]