12 citations · 93 across the 29 of their papers we have counts for
15 papers · 1 filter
On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
Tiange Li, Yinan Li, Youming Qiao +2
In Grochow and Qiao (SIAM J. Comput., 2021), the complexity class Tensor Isomorphism (TI) was introduced and isomorphism problems for groups, algebras, and polynomials were shown t…
On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications
Joshua A. Grochow, Youming Qiao
Many isomorphism problems for tensors, groups, algebras, and polynomials were recently shown to be equivalent to one another under polynomial-time reductions, prompting the introdu…
On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups
Zhili Chen, Joshua A. Grochow, Youming Qiao +2
We study the complexity of isomorphism problems for d-way arrays, or tensors, under natural actions by classical groups such as orthogonal, unitary, and symplectic groups. Such pro…
Symbolic determinant identity testing and non-commutative ranks of matrix Lie algebras
Gábor Ivanyos, Tushant Mittal, Youming Qiao
One approach to make progress on the symbolic determinant identity testing (SDIT) problem is to study the structure of singular matrix spaces. After settling the non-commutative ra…
Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions
Joshua A. Grochow, Youming Qiao
In this paper we consider the problems of testing isomorphism of tensors, -groups, cubic forms, algebras, and more, which arise from a variety of areas, including machine learni…
Incorporating Weisfeiler-Leman into algorithms for group isomorphism
Peter A. Brooksbank, Joshua A. Grochow, Yinan Li +2
In this paper we combine many of the standard and more recent algebraic techniques for testing isomorphism of finite groups (GpI) with combinatorial techniques that have typically…
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz
Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao +2
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 gr…
Boundaries of VP and VNP
Joshua A. Grochow, Ketan D. Mulmuley, Youming Qiao
One fundamental question in the context of the geometric complexity theory approach to the VP vs. VNP conjecture is whether VP = , where VP is the class of…
Constructive noncommutative rank computation is in deterministic polynomial time
Gábor Ivanyos, Youming Qiao, K. V. Subrahmanyam
We extend our techniques developed in our earlier paper appeared in Computational Complexity, 2017 (preprint: arXiv:1508.00690) to obtain a deterministic polynomial time algorithm…
On generating the ring of matrix semi-invariants
Gábor Ivanyos, Youming Qiao, K. V. Subrahmanyam
For a field , let be the ring of invariant polynomials for the action of on tuples of matrices…
Sparse multivariate polynomial interpolation in the basis of Schubert polynomials
Priyanka Mukhopadhyay, Youming Qiao
Schubert polynomials were discovered by A. Lascoux and M. Schützenberger in the study of cohomology rings of flag manifolds in 1980's. These polynomials generalize Schur polynomial…
On the Complexity of Trial and Error for Constraint Satisfaction Problems
Gábor Ivanyos, Raghav Kulkarni, Youming Qiao +2
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 wh…
Generalized Wong sequences and their applications to Edmonds' problems
Gábor Ivanyos, Marek Karpinski, Youming Qiao +1
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 linea…
Deterministic Black-Box Identity Testing -Ordered Algebraic Branching Programs
Maurice Jansen, Youming Qiao, Jayalal Sarma
In this paper we study algebraic branching programs (ABPs) with restrictions on the order and the number of reads of variables in the program. Given a permutation of variab…
Deterministic Identity Testing of Read-Once Algebraic Branching Programs
Maurice Jansen, Youming Qiao, Jayalal Sarma
In this paper we study polynomial identity testing of sums of read-once algebraic branching programs (-RO-ABPs), generalizing the work in (Shpilka and Volkovich 2008,2009)…