UTS site search

# Dr Youming Qiao

### Biography

Youming Qiao obtained his PhD in computer science from the Institute for Interdisciplinary Sciences, Tsinghua University in 2012. His advisor was Andrew Yao. Before that, he obtained his bachelor's degree in computer science from Tsinghua University. After working as a postdoc in the Centre for Quantum Technologies, National University of Singapore, he is currently a lecturer at the Centre for Quantum Computation & Intelligent Systems, University of Technology, Sydney.

### Professional

Discovery Early Career Researcher Award, Australian Research Council, to commence in 2015.

Project title: Algorithms and complexity for testing isomorphism of algebraic structures

Jiang NanXiang Scholarship (First Grade at Tsinghua University), Tsinghua University, 2011.

Senior Lecturer, School of Software
Core Member, Centre for Quantum Software and Information
BA Eng (Tsinghua Uni), PhD Eng (Tsinghua Uni)

Phone
+61 2 9514 4771
ORCID

### Research Interests

Complexity theory and algebraic computation, with an emphasis on the interaction with
group theory.
Can supervise: Yes
Algorithms, complexity, algebra, group theory.

## Conferences

Grochow, J.A., Mulmuley, K.D. & Qiao, Y. 2016, 'Boundaries of VP and VNP', Leibniz International Proceedings in Informatics, LIPIcs, International Colloquium on Automata, Languages, and Programming (ICALP), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Rome, Italy.
One fundamental question in the context of the geometric complexity theory approach to the VP vs. VNP conjecture is whether VP = !VP, where VP is the class of families of polynomials that can be computed by arithmetic circuits of polynomial degree and size, and VP is the class of families of polynomials that can be approximated infinitesimally closely by arithmetic circuits of polynomial degree and size. The goal of this article is to study the conjecture in (Mulmuley, FOCS 2012) that !VP is not contained in VP. Towards that end, we introduce three degenerations of VP (i.e., sets of points in VP), namely the stable degeneration Stable-VP, the Newton degeneration Newton-VP, and the p-definable one-parameter degeneration VP*. We also introduce analogous degenerations of VNP. We show that Stable-VP subseteq Newton-VP subseteq VP* subseteq VNP, and Stable-VNP = Newton-VNP = VNP* = VNP. The three notions of degenerations and the proof of this result shed light on the problem of separating VP from VP. Although we do not yet construct explicit candidates for the polynomial families in !VP\VP, we prove results which tell us where not to look for such families. Specifically, we demonstrate that the families in Newton-VP \VP based on semi-invariants of quivers would have to be nongeneric by showing that, for many finite quivers (including some wild ones), Newton degeneration of any generic semi-invariant can be computed by a circuit of polynomial size. We also show that the Newton degenerations of perfect matching Pfaffians, monotone arithmetic circuits over the reals, and Schur polynomials have polynomial-size circuits.
Kulkarni, R., Qiao, Y. & Sun, X. 2015, 'On the Power of Parity Queries in Boolean Decision Trees', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 12th Annual Conference, TAMC 2015, Springer, Singapore, pp. 99-109.
&copy; Springer International Publishing Switzerland 2015. In an influential paper,Kushilevitz and Mansour (1993) introduced a natural extension of Boolean decision trees called parity decision tree (PDT) where one may query the sum modulo 2, i.e., the parity, of an arbitrary subset of variables. Although originally introduced in the context of learning, parity decision trees have recently regained interest in the context of communication complexity (cf. Shi and Zhang 2010) and property testing (cf. Bhrushundi, Chakraborty, and Kulkarni 2013). In this paper, we investigate the power of parity queries. In particular, we show that the parity queries can be replaced by ordinary ones at the cost of the total influence aka average sensitivity per query. Our simulation is tight as demonstrated by the parity function. At the heart of our result lies a qualitative extension of the result of O'Donnell, Saks, Schramme, and Servedio (2005) titled: Every decision tree has an influential variable. Recently Jain and Zhang (2011) obtained an alternate proof of the same. Our main contribution in this paper is a simple but surprising observation that the query elimination method of Jain and Zhang can indeed be adapted to eliminate, seemingly much more powerful, parity queries. Moreover, we extend our result to linear queries for Boolean valued functions over arbitrary finite fields.
Ivanyos, G., Karpinski, M., Qiao, Y. & Santha, M. 2014, 'Generalized Wong sequences and their applications to Edmonds' problems', Leibniz International Proceedings in Informatics, LIPIcs, pp. 397-408.
Grochow, J.A. & Qiao, Y. 2014, 'Algorithms for group isomorphism via group extensions and cohomology', Proceedings of the Annual IEEE Conference on Computational Complexity, pp. 110-119.
Decker, T., Ivanyos, G., Kulkarni, R., Qiao, Y. & Santha, M. 2014, 'An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 226-238.
Ivanyos, G., Kulkarni, R., Qiao, Y., Santha, M. & Sundaram, A. 2014, 'On the complexity of trial and error for constraint satisfaction problems', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 663-675.
Qiao, Y., Sun, X. & Yu, N. 2013, 'Determinantal Complexities and Field Extensions', LNCS - Algorithms and Computation - Proceedings of the 24th International Symposium, ISAAC 2013, ISAAC, Springer, Hong Kong, pp. 119-129.
Let F be a field of characteristic ??2. The determinantal complexity of a polynomial P?F[x1,,xn] is defined as the smallest size of a matrix M whose entries are linear polynomials of x i s over F, such that P=det(M) as polynomials in F[x1,,xn]. To determine the determinantal complexity of the permanent polynomial is a long-standing open problem. Let K be an extension field of F; then P can be viewed as a polynomial over K. We are interested in the comparison between the determinantal complexity of P over K (denoted as dcK(P)), and that of P over F (denoted as dcF(P)). It is clear that dcK(P)=dcF(P), and the question is whether strict inequality can happen. In this note we consider polynomials defined over Q.
Kulkarni, R., Qiao, Y. & Sun, X. 2013, 'Any monotone property of 3-uniform hypergraphs is weakly evasive', LNCS - Theory and Applications of Models of Computation - Proceedings of the10th International Conference, TAMC 2013, Theory and Applications of Models of Computation, Springer, Hong Kong, pp. 224-235.
Our proof combines the combinatorial approach of Rivest and Vuillemin with the topological approach of Kahn, Saks, and Sturtevant. Interestingly, our proof makes use of Vinogradovs Theorem (weak Goldbach Conjecture), inspired by its recent use by Babai et. al. [1] in the context of the topological approach. Our work leaves the generalization to k-uniform hypergraphs as an intriguing open question.
Gupta, A., Kayal, N. & Qiao, Y. 2013, 'Random arithmetic formulas can be reconstructed efficiently', Proceedings of the Annual IEEE Conference on Computational Complexity, pp. 1-9.
Babai, L., Codenotti, P. & Qiao, Y. 2012, 'Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups', LNCS - Automata, Languages, and Programming - Proceedings, Part I of the 39th International Colloquium on Automata, Languages and Programming, International Colloquium on Automata, Languages and Programming, Springer, Warwick, UK, pp. 51-62.
We consider the problem of testing isomorphism of groups of order n given by Cayley tables. The trivial n logn bound on the time complexity for the general case has not been improved upon over the past four decades. We demonstrate that the obstacle to efficient algorithms is the presence of abelian normal subgroups; we show this by giving a polynomial-time isomorphism test for groups without nontrivial abelian normal subgroups. This concludes a project started by the authors and J. A. Grochow (SODA 2011). Two key new ingredient are: (a) an algorithm to test permutational isomorphism of permutation groups in time, polynomial in the order and simply exponential in the degree; (b) the introduction of the twisted code equivalence problem, a generalization of the classical code equivalence problem by admitting a group action on the alphabet. Both of these problems are of independent interest
Babai, L. & Qiao, Y. 2012, 'Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers', 29th Symposium on Theoretical Aspects of Computer Science, Symposium on Theoretical Aspects of Computer Science, Dagstuhl Publishing, Paris, France, pp. 453-465.
We consider the problem of testing isomorphism of groups of order n given by Cayley tables. The trivial n^{log n} bound on the time complexity for the general case has not been improved over the past four decades. Recently, Babai et al. (following Babai et al. in SODA 2011) presented a polynomial-time algorithm for groups without abelian normal subgroups, which suggests solvable groups as the hard case for group isomorphism problem. Extending recent work by Le Gall (STACS 2009) and Qiao et al. (STACS 2011), in this paper we design a polynomial-time algorithm to test isomorphism for the largest class of solvable groups yet, namely groups with abelian Sylow towers, defined as follows. A group G is said to possess a Sylow tower, if there exists a normal series where each quotient is isomorphic to Sylow subgroup of G. A group has an abelian Sylow tower if it has a Sylow tower and all its Sylow subgroups are abelian. In fact, we are able to compute the coset of isomorphisms of groups formed as coprime extensions of an abelian group, by a group whose automorphism group is known. The mathematical tools required include representation theory, Wedderburn's theorem on semisimple algebras, and M.E. Harris's 1980 work on p'-automorphisms of abelian p-groups. We use tools from the theory of permutation group algorithms, and develop an algorithm for a parameterized versin of the graph-isomorphism-hard setwise stabilizer problem, which may be of independent interest
Babai, L., Codenotti, P., Grochow, J.A. & Qiao, Y. 2011, 'Code equivalence and group isomorphism', Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithm, Annual ACM-SIAM symposium on Discrete Algorithm, ACM, San Francisco, USA, pp. 1395-1408.
The isomorphism problem for groups given by their multiplication tables has long been known to be solvable in time nlog n+O(1). The decades-old quest for a polynomial-time algorithm has focused on the very difficult case of class-2 nilpotent groups (groups whose quotient by their center is abelian), with little success. In this paper we consider the opposite end of the spectrum and initiate a more hopeful program to find a polynomial-time algorithm for semisimple groups, defined as groups without abelian normal subgroups. First we prove that the isomorphism problem for this class can be solved in time nO(log log n). We then identify certain bottlenecks to polynomial-time solvability and give a polynomial-time solution to a rich subclass, namely the semisimple groups where each minimal normal subgroup has a bounded number of simple factors. We relate the results to the filtration of groups introduced by Babai and Beals (1999). One of our tools is an algorithm for equivalence of (not necessarily linear) codes in simply-exponential time in the length of the code, obtained by modifying Luks's algorithm for hypergraph isomorphism in simply-exponential time in the number of vertices (FOCS 1999). We comment on the complexity of the closely related problem of permutational isomorphism of permutation groups.
Jansen, M., Qiao, Y. & Sarma, M.N.J. 2010, 'Deterministic Black-Box Identity Testing pi-Ordered Algebraic Branching Programs', IARCS International Conference on Foundations of Software Technology and Theoretical Computer Science, International Conference on Foundations of Software Technology and Theoretical Computer Science, Dagstuhl Publishing, Mumbai, India, pp. 296-307.
In this paper we study algebraic branching programs (ABPs) with restrictions on the order and the number of reads of variables in the program. An ABP is given by a layered directed acyclic graph with source $s$ and sink $t$, whose edges are labeled by variables taken from the set $\{x_1, x_2, \ldots, x_n\}$ or field constants. It computes the sum of weights of all paths from $s$ to $t$, where the weight of a path is defined as the product of edge-labels on the path. Given a permutation $\pi$ of the $n$ variables, for a $\pi$-ordered ABP ($\pi$-OABP), for any directed path $p$ from $s$ to $t$, a variable can appear at most once on $p$, and the order in which variables appear on $p$ must respect $\pi$. One can think of OABPs as being the arithmetic analogue of ordered binary decision diagrams (OBDDs). We say an ABP $A$ is of read $r$, if any variable appears at most $r$ times in $A$. Our main result pertains to the polynomial identity testing problem, i.e. the problem of deciding whether a given $n$-variate polynomial is identical to the zero polynomial or not. We prove that over any field $\F$, and in the black-box model, i.e. given only query access to the polynomial, read $r$ $\pi$-OABP computable polynomials can be tested in $\DTIME[2^{O(r\log r \cdot \log^2 n \log\log n)}]$. In case $\F$ is a finite field, the above time bound holds provided the identity testing algorithm is allowed to make queries to extension fields of $\F$.
Qiao, Y., Jayalal, S.M.N. & Tang, B. 2011, 'On isomorphism testing of groups with normal hall subgroups', Leibniz International Proceedings in Informatics, LIPIcs, pp. 567-578.
Bogdanov, A. & Qiao, Y. 2009, 'On the security of Goldreich's one-way function', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 392-405.
Qiao, Y. & Tartary, C. 2008, 'Counting Method for Multi-party Computation over Non-abelian Groups', LNCS - Cryptology and Network Security - Proceedings of the 7th International Conference, Cryptology and Network Security, Springer, Hong Kong, pp. 162-177.
In the Crypto'07 paper [5], Desmedt et al. studied the problem of achieving secure n-party computation over non-Abelian groups. The function to be computed is f G (x 1,...,x n ) :?=?x 1 ...x n where each participant P i holds an input x i from the non-commutative group G. The settings of their study are the passive adversary model, information-theoretic security and black-box group operations over G. They presented three results. The first one is that honest majority is needed to ensure security when computing f G . Second, when the number of adversary t=?n2?-1, they reduced building such a secure protocol to a graph coloring problem and they showed that there exists a deterministic secure protocol computing f G using exponential communication complexity. Finally, Desmedt et al. turned to analyze random coloring of a graph to show the existence of a probabilistic protocol with polynomial complexity when t?<?n/&micro;, in which &micro; is a constant less than 2.948

## Journal articles

Mukhopadhyay, P. & Qiao, Y. 2017, 'Sparse multivariate polynomial interpolation on the basis of Schubert polynomials', Computational Complexity, pp. 1-29.
&copy; 2016 Springer International PublishingSchubert polynomials were discovered by A. Lascoux and M. Sch&uuml;tzenberger in the study of cohomology rings of flag manifolds in 1980s. These polynomials generalize Schur polynomials and form a linear basis of multivariate polynomials. In 2003, Lenart and Sottile introduced skew Schubert polynomials, which generalize skew Schur polynomials and expand in the Schubert basis with the generalized Littlewood&#8211;Richardson coefficients. In this paper, we initiate the study of these two families of polynomials from the perspective of computational complexity theory. We first observe that skew Schubert polynomials, and therefore Schubert polynomials, are in #P (when evaluating on nonnegative integral inputs) and VNP. Our main result is a deterministic algorithm that computes the expansion of a polynomial f of degree d in (Formula presented.) on the basis of Schubert polynomials, assuming an oracle computing Schubert polynomials. This algorithm runs in time polynomial in n, d, and the bit size of the expansion. This generalizes, and derandomizes, the sparse interpolation algorithm of symmetric polynomials in the Schur basis by Barvinok and Fomin (Adv Appl Math 18(3):271&#8211;285, 1997). In fact, our interpolation algorithm is general enough to accommodate any linear basis satisfying certain natural properties. Applications of the above results include a new algorithm that computes the generalized Littlewood&#8211;Richardson coefficients.
Ivanyos, G., Qiao, Y. & Subrahmanyam, K.V. 2016, 'Non-commutative Edmonds' problem and matrix semi-invariants', Computational Complexity, pp. 1-47.
Ivanyos, G., Karpinski, M., Qiao, Y. & Santha, M. 2015, 'Generalized Wong sequences and their applications to Edmonds' problems', Journal of Computer and System Sciences, vol. 81, no. 7, pp. 1373-1386.
Kulkarni, R., Qiao, Y. & Sun, X. 2015, 'Any monotone property of 3-uniform hypergraphs is weakly evasive', Theoretical Computer Science, vol. 588, pp. 16-23.
In this paper, we provide a characterization of multipartite entanglement in terms of equivalence classes of states under local unitary transformation (LU) by demonstrating a simple method to construct all homogenous polynomials that are invariant under local unitary group(LUIPs) for any fixed degree. We give an upper bound on the degree of the LUIP such that the ring of LUIPs can be generated by LUIPs with degree lower than the bound. Our characterization can directly generate an algorithm whose output is a generating set of LUIPs. By employing the concept of LUIPs, we prove that multipartite entanglement is additive in the sense that two multipartite states are LU equivalent if and only if $n$-copies of these two states are LU equivalent for some $n$. The method for studying LU equivalence is also used to classify the different types of multipartite mixed entanglement according to equivalence classes of states under stochastic local operations and classical communication (SLOCC), where the pure states case was previously studied by Gour and Wallach using another approach.