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

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.
View/Download from: UTS OPUS or Publisher's site
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.
View/Download from: Publisher's site
© 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.
View/Download from: Publisher's site
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.
View/Download from: Publisher's site
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.
View/Download from: Publisher's site
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.
View/Download from: Publisher's site
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.
View/Download from: UTS OPUS or Publisher's site
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.
View/Download from: UTS OPUS or Publisher's site
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.
View/Download from: Publisher's site
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.
View/Download from: UTS OPUS or Publisher's site
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.
View/Download from: UTS OPUS or Publisher's site
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.
View/Download from: UTS OPUS
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.
View/Download from: UTS OPUS or Publisher's site
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.
View/Download from: Publisher's site
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.
View/Download from: Publisher's site
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.
View/Download from: UTS OPUS or Publisher's site
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.
View/Download from: Publisher's site
&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.
View/Download from: UTS OPUS or Publisher's site
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.
View/Download from: Publisher's site
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.
View/Download from: UTS OPUS or Publisher's site
Gupta, A., Kayal, N. & Qiao, Y. 2014, 'Random arithmetic formulas can be reconstructed efficiently', computational complexity.
View/Download from: Publisher's site
Informally stated, we present here a randomized algorithm that given black-box access to the polynomial f computed by an unknown/hidden arithmetic formula {symbol} reconstructs, on the average, an equivalent or smaller formula (Formula presented.) in time polynomial in the size of its output (Formula presented.).Specifically, we consider arithmetic formulas wherein the underlying tree is a complete binary tree, the leaf nodes are labeled by affine forms (i.e., degree one polynomials) over the input variables and where the internal nodes consist of alternating layers of addition and multiplication gates. We call these alternating normal form (ANF) formulas. If a polynomial f can be computed by an arithmetic formula of size s, it can also be computed by an ANF formula {symbol}, possibly of slightly larger size sO(1). Our algorithm gets as input black-box access to the output polynomial f (i.e., for any point x in the domain, it can query the black box and obtain f(x) in one step) of a random ANF formula {symbol} of size s (wherein the coefficients of the affine forms in the leaf nodes of {symbol} are chosen independently and uniformly at random from a large enough subset of the underlying field). With high probability (over the choice of coefficients in the leaf nodes), the algorithm efficiently (i.e., in time sO(1)) computes an ANF formula (Formula presented.) of size s computing f. This then is the strongest model of arithmetic computation for which a reconstruction algorithm is presently known, albeit efficient in a distributional sense rather than in the worst case. &copy; 2014 Springer Basel.
Qiao, Y., Sarma, M.N.J. & Tang, B. 2012, 'On Isomorphism Testing of Groups with Normal Hall Subgroups', Journal Of Computer Science And Technology, vol. 27, no. 4, pp. 687-701.
View/Download from: UTS OPUS or Publisher's site
A normal Hall subgroup N of a group G is a normal subgroup with its order coprime with its index. Schur-Zassenhaus theorem states that every normal Hall subgroup has a complement subgroup, that is a set of coset representatives H which also forms a subgroup of G. In this paper, we present a framework to test isomorphism of groups with at least one normal Hall subgroup, when groups are given as multiplication tables. To establish the framework, we first observe that a proof of Schur-Zassenhaus theorem is constructive, and formulate a necessary and sufficient condition for testing isomorphism in terms of the associated actions of the semidirect products, and isomorphisms of the normal parts and complement parts. We then focus on the case when the normal subgroup is abelian. Utilizing basic facts of representation theory of finite groups and a technique by Le Gall (STACS 2009), we first get an efficient isomorphism testing algorithm when the complement has bounded number of generators. For the case when the complement subgroup is elementary abelian, which does not necessarily have bounded number of generators, we obtain a polynomial time isomorphism testing algorithm by reducing to generalized code isomorphism problem, which asks whether two linear subspaces are the same up to permutation of coordinates. A solution to the latter can be obtained by a mild extension of the singly exponential (in the number of coordinates) time algorithm for code isomorphism problem developed recently by Babai et al. (SODA 2011). Enroute to obtaining the above reduction, we study the following computational problem in representation theory of finite groups: given two representations ? and t of a group H over
Bogdanov, A. & Qiao, Y. 2012, 'On the security of Goldreich's one-way function', Computational Complexity, vol. 21, no. 1, pp. 83-127.
View/Download from: UTS OPUS or Publisher's site
Goldreich (ECCC 2000) suggested a simple construction of a candidate one-way function f : {0, 1} n ? {0, 1} m where each bit of output is a fixed predicate P of a constant number d of (random) input bits. We investigate the security of this construction in the regime m = Dn, where D(d) is a sufficiently large constant. We prove that for any predicate P that correlates with either one or two of its inputs, f can be inverted with high probability.
Yu, N., Qiao, Y. & Sun, X., 'Characterization of multipartite entanglement'.
View/Download from: UTS OPUS
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.