## Youming QiaoEmail: jimmyqiao86 [at] gmail.com ## About MeI 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ó Babai. I 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). - My research from Jan 2015 to Dec 2017 is supported by a Discovery Early Career Researcher Award from the Australian Research Council.
## PublicationsIn 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. - 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] - 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] - 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] - 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] - 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] - Sparse multivariate polynomial interpolation in the basis of Schubert polynomials
Priyanka Mukhopadhyay, Youming Qiao In Computational Complexity, 26(4): 881–909 (2017). [arXiv] [DOI] - 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] - 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] - 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.) - Networked fairness in cake cutting
Xiaohui Bei, Youming Qiao, Shengyu Zhang In IJCAI 2017. [arXiv] - 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] - 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] - Boundaries of VP and VNP
Joshua A. Grochow, Ketan D. Mulmuley, Youming Qiao In ICALP 2016. [arXiv] - 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] - On the power of parity queries in boolean decision trees
Raghav Kulkarni, Youming Qiao, Xiaoming Sun In TAMC 2015. [Link] - Polynomial-time isomorphism test of groups that are tame extensions - (Extended Abstract)
Joshua A. Grochow, Youming Qiao In ISAAC 2015. [arXiv] - 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] - Determinantal complexities and field extensions
Youming Qiao, Xiaoming Sun, Nengkun Yu In ISAAC 2013. [PDF] - 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] - 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] - 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] - Polynomial-time isomorphism test for groups with no abelian normal subgroups
László Babai, Paolo Codenotti, Youming Qiao In ICALP 2012. [PDF] - Polynomial-time isomorphism test for groups with abelian Sylow towers
László Babai, Youming Qiao In STACS 2012. [PDF] - Code equivalence and group isomorphism
László Babai, Paolo Codenotti, Joshua A. Grochow, Youming Qiao In SODA 2011. [PDF] - Deterministic black-box identity testing π-ordered algebraic branching programs
Maurice Jansen, Youming Qiao, Jayalal M.N. Sarma In FSTTCS 2010. [arXiv], [ECCC] - Counting method for multiparty computation over non-abelian groups
Youming Qiao, Christophe Tartary In CANS 2008.
## Preprints and conference talks |