4 papers · 1 filter
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…
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…
Two-State Spin Systems with Negative Interactions
Yumou Fei, Leslie Ann Goldberg, Pinyan Lu
We study the approximability of computing the partition functions of two-state spin systems. The problem is parameterized by a symmetric matrix. Previous results on thi…