12 citations · 93 across the 29 of their papers we have counts for
38 papers
Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids
Shi Fu, Youming Qiao, Dacheng Tao +2
Over the past decade, a growing body of research has shown that -weak submodularity broadly arises in numerous subset selection tasks, including feature selection, neural networ…
Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses
Huibo Xu, Shi Fu, Youming Qiao +1
Graph matrices encode dependencies in random matrices built from shared random variables and arise in spectral algorithms, sum-of-squares (SoS), and high-dimensional statistics. We…
Synchronization Strings over the Optimal Alphabet
Huibo Xu, Shi Fu, Youming Qiao +1
Synchronization strings provide deterministic position labels for recovering coordinates after insertions and deletions. Haeupler and Shahrasbi introduced these objects, and subseq…
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…
Connections between graphs and matrix spaces
Yinan Li, Youming Qiao, Avi Wigderson +2
Given a bipartite graph , the graphical matrix space consists of matrices whose non-zero entries can only be at those positions corresponding to edges in . Tu…
The isomorphism problem for plain groups is in
Heiko Dietrich, Murray Elder, Adam Piggott +2
Testing isomorphism of infinite groups is a classical topic, but from the complexity theory viewpoint, few results are known. S{é}nizergues and the fifth author (ICALP2018) proved…
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…
Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms
Joshua A. Grochow, Youming Qiao, Gang Tang
We study the problems of testing isomorphism of polynomials, algebras, and multilinear forms. Our first main results are average-case algorithms for these problems. For example, we…
Enumerating alternating matrix spaces over finite fields with explicit coordinates
Youming Qiao
We initiate the study of enumerating linear subspaces of alternating matrices over finite fields with explicit coordinates. We postulate that this study can be viewed as a linear a…
Turán and Ramsey problems for alternating multilinear maps
Youming Qiao
Guided by the connections between hypergraphs and exterior algebras, we study Turán and Ramsey type problems for alternating multilinear maps. This study lies at the intersection o…
On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions
Xiaoyu He, Youming Qiao
Let be an odd prime. From a simple undirected graph , through the classical procedures of Baer (Trans. Am. Math. Soc., 1938), Tutte (J. Lond. Math. Soc., 1947) and Lovász (B…
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…
Group-theoretic generalisations of vertex and edge connectivities
Yinan Li, Youming Qiao
Let be an odd prime. Let be a finite -group of class and exponent , whose commutator quotient is of order . We define two parameters for relate…
General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography
Zhengfeng Ji, Youming Qiao, Fang Song +1
Starting from the one-way group action framework of Brassard and Yung (Crypto '90), we revisit building cryptography based on group actions. Several previous candidates for one-way…
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…
From independent sets and vertex colorings to isotropic spaces and isotropic decompositions
Xiaohui Bei, Shiteng Chen, Ji Guan +2
In the 1970's, Lovász built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings (FCT 1979). A similar connection between bipartite graphs and…
An improved diameter bound for finite simple groups of Lie type
Zoltán Halasi, Attila Maróti, László Pyber +1
For a finite group , let denote the maximum diameter of a connected Cayley graph of . A well-known conjecture of Babai states that is bo…
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…
Linear algebraic analogues of the graph isomorphism problem and the Erdős-Rényi model
Yinan Li, Youming Qiao
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…
Algorithms based on *-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing
Gábor Ivanyos, Youming Qiao
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 $(B_1, \d…
Networked Fairness in Cake Cutting
Xiaohui Bei, Youming Qiao, Shengyu Zhang
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 f…
On rank-critical matrix spaces
Yinan Li, Youming Qiao
A matrix space of size is a linear subspace of the linear space of matrices over a field . The rank of a matrix space is defined as the maximal…