## 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.

### Links

#### Can supervise: YES

#### Research Interests

Complexity theory and algebraic computation, with an emphasis on the interaction with

group theory.

#### Teaching Areas

Algorithms, complexity, algebra, group theory.

#### Publications

Qiao, Y, Sun, X & Yu, N 2020, 'Local Equivalence of Multipartite Entanglement', *IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS*, vol. 38, no. 3, pp. 568-574.View/Download from: Publisher's site

Halasi, Z, Maróti, A, Pyber, L & Qiao, Y 2019, 'An improved diameter bound for finite simple groups of Lie type', *Bulletin of the London Mathematical Society*, vol. 51, no. 4, pp. 645-657.View/Download from: Publisher's site

#### View description

© 2019 London Mathematical Society For a finite group (Formula presented.), let (Formula presented.) denote the maximum diameter of a connected Cayley graph of (Formula presented.). A well-known conjecture of Babai states that (Formula presented.) is bounded by (Formula presented.) in case (Formula presented.) is a non-abelian finite simple group. Let (Formula presented.) be a finite simple group of Lie type of Lie rank (Formula presented.) over the field (Formula presented.). Babai's conjecture has been verified in case (Formula presented.) is bounded, but it is wide open in case (Formula presented.) is unbounded. Recently, Biswas and Yang proved that (Formula presented.) is bounded by (Formula presented.). We show that in fact (Formula presented.) holds. Note that our bound is significantly smaller than the order of (Formula presented.) for (Formula presented.) large, even if (Formula presented.) is large. As an application, we show that more generally (Formula presented.) holds for any subgroup (Formula presented.) of (Formula presented.), where (Formula presented.) is a vector space of dimension (Formula presented.) defined over the field (Formula presented.).

Ivanyos, G & Qiao, Y 2019, 'Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing', *SIAM Journal on Computing*, vol. 48, no. 3, pp. 926-963.View/Download from: Publisher's site

#### View description

© 2019 Society for Industrial and Applied Mathematics. We consider two basic algorithmic problems concerning tuples of (skew-)symmetric matrices. The first problem asks us to decide, given two tuples of (skew-)symmetric matrices (B1,..., Bm) and (C1,..., Cm), whether there exists an invertible matrix A such that for every i ∈ {1,..., m}, AtBiA = Ci. We show that this problem can be solved in randomized polynomial time over finite fields of odd size, the reals, and the complex numbers. The second problem asks us to decide, given a tuple of square matrices (B1,..., Bm), whether there exist invertible matrices A and D, such that for every i ∈ {1,..., m}, ABiD is (skew-)symmetric. We show that this problem can be solved in deterministic polynomial time over fields of characteristic not 2. For both problems we exploit the structure of the underlying ∗-algebras (algebras with an involutive antiautomorphism) and utilize results and methods from the module isomorphism problem. Applications of our results range from multivariate cryptography to group isomorphism and to polynomial identity testing. Specifically, these results imply efficient algorithms for the following problems. (1) Test isomorphism of quadratic forms with one secret over a finite field of odd size. This problem belongs to a family of problems that serves as the security basis of certain authentication schemes proposed by Patarin [J. Patarin, in Advances in Cryptology, EUROCRYPT'96, Springer, Berlin, 1996, pp. 33-48]. (2) Test isomorphism of p-groups of class 2 and exponent p (p odd) with order p in time polynomial in the group order, when the commutator subgroup is of order pO(). (3) Deterministically reveal two families of singularity witnesses caused by the skew-symmetric structure. This represents a natural next step for the polynomial identity testing problem, in the direction set up by the recent resolution of the noncommutative rank problem [A. Garg et al., in Proceedings of the 57th Annual IEEE Sy...

Ivanyos, G, Kulkarni, R, Qiao, Y, Santha, M & Sundaram, A 2018, 'On the complexity of trial and error for constraint satisfaction problems', *Journal of Computer and System Sciences*, vol. 92, pp. 48-64.View/Download from: Publisher's site

#### View description

© 2017 Elsevier Inc. In 2013 Bei, Chen and Zhang introduced a trial and error model of computing, 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, by adopting a formal framework for CSPs, and defining several types of revealing oracles. Our main contribution is to develop a transfer theorem for each type of the revealing oracle. To any hidden CSP with a specific type of revealing oracle, the transfer theorem associates another 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 to the study of normal CSPs. We apply the transfer theorems to get polynomial-time algorithms or hardness results for several families of concrete problems.

Ivanyos, G, Qiao, Y & Subrahmanyam, KV 2018, 'CONSTRUCTIVE NON-COMMUTATIVE RANK COMPUTATION IS IN DETERMINISTIC POLYNOMIAL TIME', *COMPUTATIONAL COMPLEXITY*, vol. 27, no. 4, pp. 561-593.View/Download from: Publisher's site

Li, Y, Qiao, Y, Wang, X & Duan, R 2018, 'Tripartite-to-Bipartite Entanglement Transformation by Stochastic Local Operations and Classical Communication and the Structure of Matrix Spaces', *Communications in Mathematical Physics*, vol. 358, no. 2, pp. 791-814.View/Download from: Publisher's site

#### View description

© 2018, Springer-Verlag GmbH Germany, part of Springer Nature. We study the problem of transforming a tripartite pure state to a bipartite one using stochastic local operations and classical communication (SLOCC). It is known that the tripartite-to-bipartite SLOCC convertibility is characterized by the maximal Schmidt rank of the given tripartite state, i.e. the largest Schmidt rank over those bipartite states lying in the support of the reduced density operator. In this paper, we further study this problem and exhibit novel results in both multi-copy and asymptotic settings, utilizing powerful results from the structure of matrix spaces. In the multi-copy regime, we observe that the maximal Schmidt rank is strictly super-multiplicative, i.e. the maximal Schmidt rank of the tensor product of two tripartite pure states can be strictly larger than the product of their maximal Schmidt ranks. We then provide a full characterization of those tripartite states whose maximal Schmidt rank is strictly super-multiplicative when taking tensor product with itself. Notice that such tripartite states admit strict advantages in tripartite-to-bipartite SLOCC transformation when multiple copies are provided. In the asymptotic setting, we focus on determining the tripartite-to-bipartite SLOCC entanglement transformation rate. Computing this rate turns out to be equivalent to computing the asymptotic maximal Schmidt rank of the tripartite state, defined as the regularization of its maximal Schmidt rank. Despite the difficulty caused by the super-multiplicative property, we provide explicit formulas for evaluating the asymptotic maximal Schmidt ranks of two important families of tripartite pure states by resorting to certain results of the structure of matrix spaces, including the study of matrix semi-invariants. These formulas turn out to be powerful enough to give a sufficient and necessary condition to determine whether a given tripartite pure state can be transformed to the bipa...

Grochow, JA & Qiao, Y 2017, 'ALGORITHMS FOR GROUP ISOMORPHISM VIA GROUP EXTENSIONS AND COHOMOLOGY', *SIAM JOURNAL ON COMPUTING*, vol. 46, no. 4, pp. 1153-1216.View/Download from: Publisher's site

Ivanyos, G, Qiao, Y & Subrahmanyam, KV 2017, 'Non-commutative Edmonds’ problem and matrix semi-invariants', *Computational Complexity*, vol. 26, no. 3, pp. 717-763.View/Download from: Publisher's site

#### View description

© 2016, Springer International Publishing. In 1967, J. Edmonds introduced the problem of computing the rank over the rational function field of an n× n 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–314, 1973), matrix spaces of low rank (Fortin-Reutenauer in Sémin Lothar Comb 52:B52f 2004), Edmonds’ original problem (Gurvits in J Comput Syst Sci 69(3):448–484, 2004), and more recently, non-commutative arithmetic circuits with divisions (Hrubeš 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 F-algebra of matrix semi-invariants, denoted as R(n, m). For a field F, it is the ring of invariant polynomials for the action of SL (n, F) × SL (n, F) on tuples of matrices—(A, C) ∈ SL (n, F) × SL (n, F) sends (B 1 , … , B m ) ∈ M(n, F) ⊕ m to (AB 1 C T , … , AB m C T ). 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 ≤ σ, then there follows a poly (n, σ) -time randomized algorithm to decide whether the non-commutative rank of T is full. To our knowledge, previously the best bound for σ was O(n2·4n2) over algebraically closed fields of characteristic 0 (Derksen in Proc Am Math Soc 129(4):955–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 σ for R(n, m) over Q, deciding whether or not T has non-commutative rank < n over Q can be done deterministically in time polynomial in the input size and σ.When F is large enough, we devise an a...

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

#### View description

© 2016 Springer International PublishingSchubert polynomials were discovered by A. Lascoux and M. Schü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–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–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–Richardson coefficients.

Li, Y & Qiao, Y 2017, 'On rank-critical matrix spaces', *Differential Geometry and its Application*, vol. 55, pp. 68-77.View/Download from: Publisher's site

#### View description

© 2017 Elsevier B.V. A matrix space of size m×n is a linear subspace of the linear space of m×n matrices over a field F. The rank of a matrix space is defined as the maximal rank over matrices in this space. A matrix space A is called rank-critical, if any matrix space which properly contains it has rank strictly greater than that of A. In this note, we first exhibit a necessary and sufficient condition for a matrix space A to be rank-critical, when F is large enough. This immediately implies the sufficient condition for a matrix space to be rank-critical by Draisma (2006) [5], albeit requiring the field to be slightly larger. We then study rank-critical spaces in the context of compression and primitive matrix spaces. We first show that every rank-critical matrix space can be decomposed into a rank-critical compression matrix space and a rank-critical primitive matrix space. We then prove, using our necessary and sufficient condition, that the block-diagonal direct sum of two rank-critical matrix spaces is rank-critical if and only if both matrix spaces are primitive, when the field is large enough.

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

#### View description

© 2015 Elsevier Inc. Given a linear subspace B of the n×n 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: Publisher's site

#### View description

© 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*, vol. 23, no. 2, pp. 207-303.View/Download from: Publisher's site

#### View description

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. © 2014 Springer Basel.

Yu, N, Qiao, Y & Sun, X 2014, 'Characterization of multipartite entanglement', pp. 1-6.

#### View description

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.

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: Publisher's site

#### View description

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.

Qiao, Y, Sarma, MNJ & 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: Publisher's site

#### View description

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

Grochow, JA & Qiao, Y 2015, 'Polynomial-Time Isomorphism Test of Groups that are Tame Extensions' in *Algorithms and Computation*, Springer Berlin Heidelberg, pp. 578-589.View/Download from: Publisher's site

Qiao, Y, Ji, Z, Yun, A & Song, F 2019, 'General Linear Group Action on Tensors: A Candidate for Post-quantum Cryptography', Theory of Cryptography - 17th International Conference, Nuremberg.View/Download from: Publisher's site

Ivanyos, G & Qiao, Y 2018, 'Algorithms based on ∗-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing', *Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms*, Symposium on Discrete Algorithm, ACM, New Orleans, LA, USA, pp. 2357-2376.View/Download from: Publisher's site

#### View description

© Copyright 2018 by SIAM. We consider two basic algorithmic problems concerning tuples of (skew-)symmetric matrices. The first problem asks to decide, given two tuples of (skew-)symmetric matrices (B1; : : : ;Bm) and (C1; : : : ;Cm), whether there exists an invertible matrix A such that for every i 2 f1; : : : ;mg, AtBiA = Ci. We show that this problem can be solved in randomized polynomial time over finite fields of odd size, the reals, and the complex numbers. The second problem asks to decide, given a tuple of square matrices (B1; : : : ;Bm), whether there exist invertible matrices A and D, such that for every i 2 f1; : : : ;mg, ABiD is (skew-)symmetric. We show that this problem can be solved in deterministic polynomial time over fields of characteristic not 2. For both problems we exploit the structure of the underlying α-algebras (algebras with an involutive antiautomorphism), and utilize results and methods from the module isomorphism problem. Applications of our results range from multivariate cryptography, group isomorphism, to polynomial identity testing. Specifically, these results imply efficient algorithms for the following problems. (1) Test isomorphism of quadratic forms with one secret over a finite field of odd size. This problem belongs to a family of problems that serves as the security basis of certain authentication schemes proposed by Patarin (Eurocrypt 1996). (2) Test isomorphism of p-groups of class 2 and exponent p (p odd) with order p' in time polynomial in the group order, when the commutator subgroup is of order pO( p '). (3) Deterministically reveal two families of singularity witnesses caused by the skew-symmetric structure. This represents a natural next step for the polynomial identity testing problem, in the direction set up by the recent resolution of the non-commutative rank problem (Garg-Gurvits-Oliveira-Wigderson, FOCS 2016; Ivanyos-Qiao-Subrahmanyam, ITCS 2017).

Bei, X, Qiao, Y & Zhang, S 2017, 'Networked fairness in cake cutting', *IJCAI International Joint Conference on Artificial Intelligence*, pp. 3632-3638.

#### View description

We introduce a graphical framework for fair division in cake cutting, where comparisons between agents are limited by an underlying network structure. We generalize the classical fairness notions of envy-freeness and proportionality to this graphical setting. Given a simple undirected graph G, an allocation is envy-free on G if no agent envies any of her neighbor's share, and is proportional on G if every agent values her own share no less than the average among her neighbors, with respect to her own measure. These generalizations open new research directions in developing simple and efficient algorithms that can produce fair allocations under specific graph structures. On the algorithmic frontier, we first propose a moving-knife algorithm that outputs an envy-free allocation on trees. The algorithm is significantly simpler than the discrete and bounded envy-free algorithm recently designed in [Aziz and Mackenzie, 2016a] for complete graphs. Next, we give a discrete and bounded algorithm for computing a proportional allocation on descendant graphs, a class of graphs by taking a rooted tree and connecting all its ancestor-descendant pairs.

Belovs, A, Ivanyos, G, Qiao, Y, Santha, M & Yang, S 2017, 'On the polynomial parity argument complexity of the combinatorial nullstellensatz', *Leibniz International Proceedings in Informatics, LIPIcs*.View/Download from: Publisher's site

#### View description

© Aleksandrs Belovs, Gabor Ivanyos, Youming Qiao, Miklos Santha, and Siyi Yang. The complexity class PPA consists of NP-search problems which are reducible to the parity principle in undirected graphs. It contains a wide variety of interesting problems from graph theory, combinatorics, algebra and number theory, but only a few of these are known to be complete in the class. Before this work, the known complete problems were all discretizations or combinatorial analogues of topological fixed point theorems. Here we prove the PPA-completeness of two problems of radically different style. They are PPA-Circuit CNSS and PPA-Circuit Chevalley, related respectively to the Combinatorial Nullstellensatz and to the Chevalley-Warning Theorem over the two elements field F2. The input of these problems contain PPA-circuits which are arithmetic circuits with special symmetric properties that assure that the polynomials computed by them have always an even number of zeros. In the proof of the result we relate the multilinear degree of the polynomials to the parity of the maximal parse subcircuits that compute monomials with maximal multilinear degree, and we show that the maximal parse subcircuits of a PPA-circuit can be paired in polynomial time.

Ivanyos, G, Qiao, Y & Venkata Subrahmanyam, K 2017, 'Constructive non-commutative rank computation is in deterministic polynomial time', *Leibniz International Proceedings in Informatics, LIPIcs*, Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl, Berkeley, CA, USA, pp. 1-18.View/Download from: Publisher's site

#### View description

Let B be a linear space of matrices over a field F spanned by n × n matrices B1, . . . ,Bm. The non-commutative rank of B is the minimum r € N such that there exists U < Fnsatisfying dim(U) - dim(B(U)) n - r, where B(U) := span(Ui2€[m]Bi(U)). Computing the non-commutative rank generalizes some well-known problems including the bipartite graph maximum matching problem and the linear matroid intersection problem. In this paper we give a deterministic polynomial-Time algorithm to compute the non-commutative rank over any field F. Prior to our work, such an algorithm was only known over the rational number field Q, a result due to Garg et al, [20]. Our algorithm is constructive and produces a witness certifying the non-commutative rank, a feature that is missing in the algorithm from [20]. Our result is built on techniques which we developed in a previous paper [24], with a new reduction procedure that helps to keep the blow-up parameter small. There are two ways to realize this reduction. The first involves constructivizing a key result of Derksen and Makam [12] which they developed in order to prove that the null cone of matrix semi-invariants is cut out by generators whose degree is polynomial in the size of the matrices involved. We also give a second, simpler method to achieve this. This gives another proof of the polynomial upper bound on the degree of the generators cutting out the null cone of matrix semi-invariants. Both the invariant-Theoretic result and the algorithmic result rely crucially on the regularity lemma proved in [24]. In this paper we improve on the constructive version of the regularity lemma from [24] by removing a technical coprime condition that was assumed there.

Li, Y & Qiao, Y 2017, 'Linear algebraic analogues of the graph isomorphism problem and the erds-rényi model', *Annual Symposium on Foundations of Computer Science - Proceedings*, IEEE Annual Symposium on Foundations of Computer Science, IEEE, Berkeley, CA, USA, pp. 463-474.View/Download from: Publisher's site

#### View description

© 2017 IEEE. A classical difficult isomorphism testing problem is to test isomorphism of p-groups of class 2 and exponent p in time polynomial in the group order. It is known that this problem can be reduced to solving the alternating matrix space isometry problem over a finite field in time polynomial in the underlying vector space size. We propose a venue of attack for the latter problem by viewing it as a linear algebraic analogue of the graph isomorphism problem. This viewpointleads us to explore the possibility of transferring techniques for graph isomorphism to this long-believed bottleneck case of group isomorphism.In 1970s, Babai, Erds, and Selkow presented the first average-case efficient graph isomorphism testing algorithm (SIAM J Computing, 1980). Inspired by that algorithm, we devise an average-case efficient algorithm for the alternating matrix space isometry problem over a key range of parameters, in a random model of alternating matrix spaces in vein of the Erdos-R4;enyi model of random graphs. For this, we develop a linear algebraic analogue of the classical individualisation technique, a technique belonging to a set of combinatorial techniques that has been critical for the progress on the worst-case time complexity for graph isomorphism, but was missing in the group isomorphism context. This algorithm also enables us to improve Higmans 57-year-old lower bound on the number of p-groups (Proc. of the LMS, 1960). We finally show that Luks dynamic programming technique for graph isomorphism (STOC 1999) can be adapted to slightly improve the worst-case time complexity of the alternating matrix space isometry problem in a certain range of parameters.Most notable progress on the worst-case time complexity of graph isomorphism, including Babais recent breakthrough (STOC 2016) and Babai and Luks previous record (STOC 1983), has relied on both group theoretic and combinatorial techniques. By developing a linear algebraic analogue of the individualisation ...

Grochow, JA, Mulmuley, KD & Qiao, Y 2016, 'Boundaries of VP and VNP', *Leibniz International Proceedings in Informatics, LIPIcs*, International Colloquium on Automata Languages and Programming, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Rome, Italy.View/Download from: Publisher's site

#### View description

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.

Grochow, JA & Qiao, Y 2015, 'Polynomial-time isomorphism test of groups that are tame extensions (Extended abstract)', *Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*, pp. 578-589.View/Download from: Publisher's site

#### View description

© Springer-Verlag Berlin Heidelberg 2015. We give new polynomial-time algorithms for testing isomorphism of a class of groups given by multiplication tables (GpI). Two results (Cannon & Holt, J. Symb. Comput. 2003; Babai, Codenotti & Qiao, ICALP 2012) imply that GpI reduces to the following: given groups G,H with characteristic subgroups of the same type and isomorphic to ℤdp , and given the coset of isomorphisms Iso(G/ℤdp ,H/ℤdp), compute Iso(G,H) in time poly(|G|). Babai&Qiao (STACS 2012) solved this problem when a Sylow p-subgroup of G/ℤdp is trivial. In this paper, we solve the preceding problem in the so-called “tame” case, i. e., when a Sylow p-subgroup of G/ℤdp is cyclic, dihedral, semi-dihedral, or generalized quaternion. These cases correspond exactly to the group algebra (Formula presented.) being of tame type, as in the celebrated tame-wild dichotomy in representation theory. We then solve new cases of GpI in polynomial time. Our result relies crucially on the divide-and-conquer strategy proposed earlier by the authors (CCC 2014), which splits GpI into two problems, one on group actions (representations), and one on group cohomology. Based on this strategy, we combine permutation group and representation algorithms with new mathematical results, including bounds on the number of indecomposable representations of groups in the tame case, and on the size of their cohomology groups. Finally, we note that when a group extension is not tame, the preceding bounds do not hold. This suggests a precise sense in which the tame-wild dichotomy from representation theory may also be a key barrier to cross to put GpI into P.

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)*, Conference on Theory and Applications of Models of Computation, Springer, Singapore, pp. 99-109.View/Download from: Publisher's site

#### View description

© 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.

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)*, International Symposium on Mathematical Foundations of Computer Science, Springer, Budapest, Hungary, pp. 226-238.View/Download from: Publisher's site

#### View description

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.

Grochow, JA & Qiao, Y 2014, 'Algorithms for group isomorphism via group extensions and cohomology', *Proceedings of the Annual IEEE Conference on Computational Complexity*, IEEE Conference on Computational Complexity, IEEE, Canada, pp. 110-119.View/Download from: Publisher's site

#### View description

The isomorphism problem for groups given by their multiplication tables (GPI) has long been known to be solvable in n O(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 n o(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 n O(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 cohomo...

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

#### View description

© 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 n×n 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.

Ivanyos, G, Kulkarni, R, Qiao, Y, Santha, M & Sundaram, A 2014, 'On the complexity of trial and error for constraint satisfaction problems',

#### View description

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.

Gupta, A, Kayal, N & Qiao, Y 2013, 'Random Arithmetic Formulas can be Reconstructed Efficiently', *2013 IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC)*, 28th Annual IEEE Conference on Computational Complexity (CCC), IEEE, Palo Alto, CA, pp. 1-9.View/Download from: Publisher's site

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: Publisher's site

#### View description

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.

Qiao, Y, Sun, X & Yu, N 2013, 'Determinantal Complexities and Field Extensions', *LNCS - Algorithms and Computation - Proceedings of the 24th International Symposium, ISAAC 2013*, International Symposium on Algorithms and Computation, Springer, Hong Kong, pp. 119-129.View/Download from: Publisher's site

#### View description

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.

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: Publisher's site

#### View description

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 & 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: Publisher's site

#### View description

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, Codenotti, P, Grochow, JA & Qiao, Y 2011, 'Code equivalence and group isomorphism', *Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithm*, ACM/SIAM Symposium on Discrete Algorithms, ACM, San Francisco, USA, pp. 1395-1408.

#### View description

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, MNJ 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, Chennai, India, pp. 296-307.View/Download from: Publisher's site

#### View description

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, Sarma, JMN & Tang, B 2011, 'On Isomorphism Testing of Groups with Normal Hall Subgroups', *28TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2011)*, 28th International Symposium on Theoretical Aspects of Computer Science (SATCS), SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS, Dortmund, GERMANY, pp. 567-578.View/Download from: Publisher's site

Bogdanov, A & Qiao, Y 2009, 'On the Security of Goldreich's One-Way Function', *APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION*, 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems/13th International Workshop on Randomization and Computation, SPRINGER-VERLAG BERLIN, Berkeley, CA, pp. 392-+.

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: Publisher's site

#### View description

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/µ, in which µ is a constant less than 2.948