12 citations · 93 across the 29 of their papers we have counts for
5 papers · 1 filter
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…