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, QCIS - Quantum Computation and Intelligent Systems
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

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
© Gábor Ivanyos, Marek Karpinski, Youming Qiao, and Miklos Santha. We design two deterministic polynomial time algorithms for variants of a problem introduced by Edmonds in 1967: determine the rank of a matrix M whose entries are homogeneous linear polynomials over the integers. Given a linear subspace B of the nn matrices over some field F, we consider the following problems: symbolic matrix rank (SMR) is the problem to determine the maximum rank among matrices in B, while symbolic determinant identity testing (SDIT) is the question to decide whether there exists a nonsingular matrix in B. The constructive versions of these problems are asking to find a matrix of maximum rank, respectively a nonsingular matrix, if there exists one. Our first algorithm solves the constructive SMR when B is spanned by unknown rank one matrices, answering an open question of Gurvits. Our second algorithm solves the constructive SDIT when B is spanned by triangularizable matrices, but the triangularization is not given explicitly. Both algorithms work over finite fields of size at least n + 1 and over the rational numbers, and the first algorithm actually solves (the non-constructive) SMR independent of the field size. Our main tool to obtain these results is to generalize Wong sequences, a classical method to deal with pairs of matrices, to the case of pairs of matrix spaces.
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
The isomorphism problem for groups given by their multiplication tables (GPI) has long been known to be solvable in nO(log n) time, but only recently has there been significant progress towards polynomial time. For example, Babai et al. (ICALP 2012) gave a polynomial-time algorithm for groups with no abelian normal subgroups. Thus, at present it is crucial to understand groups with abelian normal subgroups to develop no(log n)-time algorithms. Towards this goal we advocate a strategy via the extension theory of groups, which describes how a normal subgroup N is related to G/N via G. This strategy 'splits' GPI into two sub problems: one regarding group actions on other groups, and one regarding group co homology. The solution of these problems is essentially necessary and sufficient to solve GPI. Most previous works naturally align with this strategy, and it thus helps explain in a unified way the recent polynomial-time algorithms for other group classes. In particular, most prior results in the multiplication table model focus on the group action aspect, despite the general necessity of co homology, for example for p-groups of class 2-believed to be the hardest case of GPI. To make progress on the group co homology aspect of GPI, we consider central-radical groups, proposed in Babai et al. (SODA 2011): the class of groups such that G mod its center has no abelian normal subgroups. Recall that Babai et al. (ICALP 2012) consider the class of groups G such that G itself has no abelian normal subgroups. Following the above strategy, we solve GPI in n O(log log n) time for central-radical groups, and in polynomial time for several prominent subclasses of central-radical groups. We also solve GPI in nO(log log n)-time for groups whose solvable normal subgroups are elementary abelian but not necessarily central. As far as we are aware, this is the first time that a nontrivial algorithm with worst-case guarantees has tackled both aspects of GPI-actions and cohomology-sim...
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
In the theory of algebraic groups, parabolic subgroups form a crucial building block in the structural studies. In the case of general linear groups over a finite field, given a sequence of positive integers n 1, , n k, where n=n 1++n k, a parabolic subgroup of parameter (n 1, , n k ) in GL is a conjugate of the subgroup consisting of block lower triangular matrices where the ith block is of size n i. Our main result is a quantum algorithm of time polynomial in logq and n for solving the hidden subgroup problem in GL, when the hidden subgroup is promised to be a parabolic subgroup. Our algorithm works with no prior knowledge of the parameter of the hidden parabolic subgroup. Prior to this work, such an efficient quantum algorithm was only known for minimal parabolic subgroups (Borel subgroups), for the case when q is not much smaller than n (G. Ivanyos: Quantum Inf. Comput., Vol. 12, pp. 661-669). © 2014 Springer-Verlag Berlin Heidelberg.
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
In a recent work of Bei, Chen and Zhang (STOC 2013), a trial and error model of computing was introduced, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle which, for a candidate assignment, reveals some information about a violated constraint if the assignment is not satisfying. In this paper we initiate a systematic study of constraint satisfaction problems in the trial and error model. To achieve this, we first adopt a formal framework for CSPs, and based on this framework we define several types of revealing oracles. Our main contribution is to develop a transfer theorem for each type of the revealing oracle, under a broad class of parameters. To any hidden CSP with a specific type of revealing oracle, the transfer theorem associates another, potentially harder CSP in the normal setting, such that their complexities are polynomial time equivalent. This in principle transfers the study of a large class of hidden CSPs, possibly with a promise on the instances, to the study of CSPs in the normal setting. We then apply the transfer theorems to get polynomial-time algorithms or hardness results for hidden CSPs, including satisfaction problems, monotone graph properties, isomorphism problems, and the exact version of the Unique Games problem. © 2014 Springer-Verlag.
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
Informally stated, we present here a randomized algorithm that given blackbo access to the polynomial f computed by an unknown/hidden arithmetic formula reconstructs, on average, an equivalent or smaller formula in time polynomial in the size of its output . Specifically, we consider arithmetic formulas wherein the underlying tree is a complete binary tree, the leaf nodes are labelled 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 , possibly of slightly larger size sO(1). Our algorithm gets as input blackbo access to the output polynomial f (i.e. for any point in the domain, it can query the blackbo and obtain f() in one step) of a random ANF formula f of size s (wherein the coefficients of the affine forms in the leaf nodes of f 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 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. © 2013 IEEE.
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
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 in [9], 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. 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 in [3]. Enroute to obtaining the above reduction, we study the following computational problem in representation theory of finite groups: given two representations and of a group H over d p, p a prime, determine if there exists an automorphism : H H, such that the induced representation = o and are equivalent, in time poly(|H|,pd). © Youming Qiao, Jayalal Sarma M.N., and Bangsheng Tang.
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
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 variables, f can be inverted with high probability. We also prove an amplification claim regarding Goldreich's construction. Suppose we are given an assignment x {0, 1} n that has correlation > 0 with the hidden assignment x {0, 1} n. Then, given access to x, it is possible to invert f on x with high probability, provided D = D(d,) is sufficiently large. © 2009 Springer.
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. 2016, '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: Publisher's site
&copy; 2016 Springer International PublishingIn 1967, J. Edmonds introduced the problem of computing the rank over the rational function field of an (Formula presented.) matrix T with integral homogeneous linear polynomials. In this paper, we consider the non-commutative version of Edmonds' problem: compute the rank of T over the free skew field. This problem has been proposed, sometimes in disguise, from several different perspectives in the study of, for example, the free skew field itself (Cohn in J Symbol Log 38(2):309&#8211;314, 1973), matrix spaces of low rank (Fortin-Reutenauer in S&eacute;min Lothar Comb 52:B52f 2004), Edmonds' original problem (Gurvits in J Comput Syst Sci 69(3):448&#8211;484, 2004), and more recently, non-commutative arithmetic circuits with divisions (Hrube&#353; and Wigderson in Theory Comput 11:357-393, 2015. doi:10.4086/toc.2015.v011a014). It is known that this problem relates to the following invariant ring, which we call the (Formula presented.)-algebra of matrix semi-invariants, denoted as R(n, m). For a field (Formula presented.), it is the ring of invariant polynomials for the action of (Formula presented.) on tuples of matrices&#8212;(Formula presented.) sends (Formula presented.) to (Formula presented.). Then those T with non-commutative rank < n correspond to those points in the nullcone of R(n, m). In particular, if the nullcone of R(n, m) is defined by elements of degree (Formula presented.), then there follows a (Formula presented.)-time randomized algorithm to decide whether the non-commutative rank of T is full. To our knowledge, previously the best bound for (Formula presented.) was (Formula presented.) over algebraically closed fields of characteristic 0 (Derksen in Proc Am Math Soc 129(4):955&#8211;964, 2001). We now state the main contributions of this paper:We observe that by using an algorithm of Gurvits, and assuming the above bound (Formula presented.) for R(n, m) over (Formula presented.), deciding whether or not T has non-commutative rank < n over (F...
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
&copy; 2015 Elsevier Inc. Given a linear subspace B of the nn matrices over some field F, we consider the following problems: symbolic matrix rank (SMR) asks to determine the maximum rank among matrices in B, while symbolic determinant identity testing (SDIT) asks to decide whether there exists a nonsingular matrix in B. The constructive versions of these problems ask to find a matrix of maximum rank, respectively a nonsingular matrix, if there exists one. Our first algorithm solves the constructive SMR when B is spanned by unknown rank one matrices, answering an open question of Gurvits. Our second algorithm solves the constructive SDIT when B is spanned by triangularizable matrices. (The triangularization is not given explicitly.) Both algorithms work over fields of size n+1. Our framework is based on generalizing Wong sequences, a classical method to deal with pairs of matrices, to pairs of matrix spaces.
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
&copy; 2014 Elsevier B.V. For a Boolean function f, let D(f) denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine f. In a classic paper, Rivest and Vuillemin [11] show that any non-constant monotone property P:{0,1}(n2){0,1} of n-vertex graphs has D(P)=(n2).We extend their result to 3-uniform hypergraphs. In particular, we show that any non-constant monotone property P:{0,1}(n3){0,1} of n-vertex 3-uniform hypergraphs has D(P)=(n3).Our proof combines the combinatorial approach of Rivest and Vuillemin with the topological approach of Kahn, Saks, and Sturtevant [6]. Interestingly, our proof makes use of Vinogradov's 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. 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.