Youming Qiao

Email: jimmyqiao86 [at]

About Me

I am a senior lecturer at the Centre for Quantum Software and Information, University of Technology Sydney

I was a research fellow at the National University of Singapore, hosted by Professor Miklos Santha from 2012 to 2014. I got my Ph.D. from Institute for Interdisciplinary Information Sciences of Tsinghua University at Beijing in 2012. My advisor was Professor Andrew Yao. During my PhD study I spent about nine months as a visiting student at the University of Chicago, and did research there under the guidance of Professor László BabaiI obtained my B.S. in 2008 from the Department of Computer Science and Technology at Tsinghua University at Beijing, China.

My research interests lie in complexity theory and algebraic computation, with an emphasis on the interaction with group theory. The two problems closest to my heart are group isomorphism problem and polynomial identity testing problem. I also have interests in and have worked on problems from cryptography, decision tree complexity, and quantum information and computation.

Here is my CV (lasted updated in Jan 2016).


In the following, except those marked with *, the authors are ordered alphabetically according to their last names. This follows the tradition of mathematics and theoretical computer science.
  1. 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
    To appear in Communications in Mathematical Physics. [arXiv] [DOI]

  2. Constructive non-commutative rank is in deterministic polynomial time
    Gábor Ivanyos, Youming Qiao, K. V. Subrahmanyam
    To appear in Computational Complexity.
    In ITCS 2017. [arXiv]

  3. On the complexity of trial and error for constraint satisfaction problems
    Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram
    In Journal of Computer and System Sciences 92: 48-64 (2018). [DOI]
    In ICALP 2014. [ECCC

  4. 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
    In SODA 2018. [arXiv]

  5. Algorithms for group isomorphism via group extensions and cohomology 
    Joshua A. Grochow, Youming Qiao
    In 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.)
    In CCC 2014.  [arXiv]

  6. Sparse multivariate polynomial interpolation in the basis of Schubert polynomials
    Priyanka Mukhopadhyay, Youming Qiao
    In Computational Complexity, 26(4): 881–909 (2017). [arXiv] [DOI]

  7. Non-commutative Edmonds' problem and matrix semi-invariants
    Gábor Ivanyos, Youming Qiao, K. V. Subrahmanyam
    In Computational Complexity, 26(3): 717-763 (2017). [arXiv] [DOI]

  8. On rank-critical matrix spaces
    Yinan Li, Youming Qiao
    In Differential Geometry and its Applications, special issue in Geometry and Complexity Theory, 2017. [arXiv] [DOI]

  9. Linear algebraic analogues of the graph isomorphism problem and the Erdős-Rényi model
    Yinan Li, Youming Qiao
    In FOCS 2017. [arXiv]
    (The arXiv version 2 contains a correction to the implications to group enumeration.)

  10. Networked fairness in cake cutting
    Xiaohui Bei, Youming Qiao, Shengyu Zhang
    In IJCAI 2017. [arXiv]

  11. On the Polynomial Parity Argument complexity of the Combinatorial Nullstellensatz
    Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, Siyi Yang
    In CCC 2017. [Open Access]

  12. 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
    Accepted to Theoretical Computer Science, 2016.
    In MFCS 2014. [arXiv

  13. Boundaries of VP and VNP
    Joshua A. Grochow, Ketan D. Mulmuley, Youming Qiao
    In ICALP 2016. [arXiv]

  14. Generalized Wong sequences and their applications to Edmonds’ problems
    Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha
    In Journal of Computer and System Sciences 81(7): 1373-1386 (2015).
    In STACS 2014. [arXiv], [ECCC

  15. On the power of parity queries in boolean decision trees
    Raghav Kulkarni, Youming Qiao, Xiaoming Sun
    In TAMC 2015. [Link]

  16. Polynomial-time isomorphism test of groups that are tame extensions - (Extended Abstract)
    Joshua A. Grochow, Youming Qiao
    In ISAAC 2015. [arXiv]

  17. Random arithmetic formulas can be reconstructed efficiently 
    Ankit Gupta, Neeraj Kayal, Youming Qiao
    In Computational Complexity 23(2): 207-303 (2014).
    In CCC 2013. [ECCC]

  18. Determinantal complexities and field extensions
    Youming Qiao, Xiaoming Sun, Nengkun Yu
    In ISAAC 2013. [PDF]

  19. Any monotone property of 3-uniform hypergraphs is weakly evasive
    Raghav Kulkarni, Youming Qiao, Xiaoming Sun
    In Theoretical Computer Science 588: 16-23 (2015)
    In TAMC 2013. [PDF

  20. On the security of Goldreich’s one-way function 
    Andrej Bogdanov, Youming Qiao
    In Computational Complexity 21(1): 83-127 (2012)
    In RANDOM 2009. [PDF]

  21. On isomorphism testing of groups with normal Hall subgroups 
    Youming Qiao, Jayalal M.N. Sarma, Bangsheng Tang
    In Journal of Computer Science and Technology 27(4): 687-701 (2012)
    In STACS 2011. [PDF

  22. Polynomial-time isomorphism test for groups with no abelian normal subgroups
    László Babai, Paolo Codenotti, Youming Qiao
    In ICALP 2012. [PDF

  23. Polynomial-time isomorphism test for groups with abelian Sylow towers
    László Babai, Youming Qiao
    In STACS 2012. [PDF]

  24. Code equivalence and group isomorphism
    László Babai, Paolo Codenotti, Joshua A. Grochow, Youming Qiao
    In SODA 2011. [PDF]

  25. Deterministic black-box identity testing π-ordered algebraic branching programs
    Maurice Jansen, Youming Qiao, Jayalal M.N. Sarma
    In FSTTCS 2010. [arXiv], [ECCC]

  26. Counting method for multiparty computation over non-abelian groups
    Youming Qiao, Christophe Tartary
    In CANS 2008.

Preprints and conference talks

  • On generating the ring of matrix semi-invariants
    Gábor Ivanyos, Youming Qiao, K. V. Subrahmanyam. 2015. [arXiv]

  • Characterization of multipartite entanglement
    (*) Nengkun Yu, Youming Qiao, Xiaoming Sun. 2014. [arXiv]
  • Deterministic black-box identity testing read-once algebraic branching programs 
    Maurice Jansen, Youming Qiao, Jayalal M.N. Sarma. 2009. [arXiv], [ECCC