6 citations · 17 across the 13 of their papers we have counts for
7 papers · 1 filter
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…
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…
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…
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…