10 papers
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…
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…
Testing Bipartiteness in Logarithmic Rounds
Yumou Fei, Ronitt Rubinfeld
The seminal work of Goldreich and Ron (\textit{Combinatorica, 1999}) showed that bipartiteness of bounded-degree graphs can be tested using random walks of leng…
Near-Optimal Space Lower Bounds for Streaming CSPs
Yumou Fei, Dor Minzer, Shuo Wang
In a streaming constraint satisfaction problem (streaming CSP), a -pass algorithm receives the constraints of an instance sequentially, making passes over the input in a fix…
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…
Testing Properties of Edge Distributions
Yumou Fei
We initiate the study of distribution testing for probability distributions over the edges of a graph, motivated by the closely related question of ``edge-distribution-free'' graph…