4 papers · 1 filter
Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
Yumou Fei
The bounded-degree query model, introduced by Goldreich and Ron (\textit{Algorithmica, 2002}), is a standard framework in graph property testing and sublinear-time algorithms. Many…
A Dichotomy Theorem for Multi-Pass Streaming CSPs
Yumou Fei, Dor Minzer, Shuo Wang
We show a dichotomy result for -pass streaming algorithms for all CSPs and for up to polynomially many passes. More precisely, we prove that for any arity parameter , finite…
On the Spectral Expansion of Monotone Subsets of the Hypercube
Yumou Fei, Renato Ferreira Pinto
We study the spectral gap of subgraphs of the hypercube induced by monotone subsets of vertices. For a monotone subset of density , the previous best…
Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
Yumou Fei, Dor Minzer, Shuo Wang
In the Max-Cut problem in the streaming model, an algorithm is given the edges of an unknown graph in some fixed order, and its goal is to approximate the size of the l…