Yumou Fei

activity

20222026

collaborators

12 papers

cs.DS2026

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 $O (n lo g n)$ random walks of leng…

cs.CC2026

Near-Optimal Space Lower Bounds for Streaming CSPs

Yumou Fei, Dor Minzer, Shuo Wang

In a streaming constraint satisfaction problem (streaming CSP), a $p$ -pass algorithm receives the constraints of an instance sequentially, making $p$ passes over the input in a fix…

cs.DS2026

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…

cs.CC2025

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…

cs.CC2025

A Dichotomy Theorem for Multi-Pass Streaming CSPs

Yumou Fei, Dor Minzer, Shuo Wang

We show a dichotomy result for $p$ -pass streaming algorithms for all CSPs and for up to polynomially many passes. More precisely, we prove that for any arity parameter $k$ , finite…

math.PR2025

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 $A \subseteq {0, 1}^{n}$ of density $μ (A)$ , the previous best…

cs.DS2025

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 $G = (V, E)$ in some fixed order, and its goal is to approximate the size of the l…

cs.DS2024

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries

Xi Chen, Yumou Fei, Shyamal Patel

We give a distribution-free testing algorithm for decision lists with $O ~ (n^{11/12} / ε^{3})$ queries. This is the first sublinear algorithm for this problem, which sh…

math.CO2023

Characterizing positroid quotients of uniform matroids

Zhixing Chen, Yumou Fei, Jiyang Gao +2

We study two-step flag positroids $(P_{1}, P_{2})$ , where $P_{1}$ is a quotient of $P_{2}$ . We provide a complete characterization of all two-step flag positroids that contain a uniform…

cs.DS2023

Efficiently matching random inhomogeneous graphs via degree profiles

Jian Ding, Yumou Fei, Yuanzheng Wang

In this paper, we study the problem of recovering the latent vertex correspondence between two correlated random graphs with vastly inhomogeneous and unknown edge probabilities bet…

cs.CC2023

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 $2 \times 2$ symmetric matrix. Previous results on thi…

cs.GT2022

Improved Approximation to First-Best Gains-from-Trade

Yumou Fei

We study the two-agent single-item bilateral trade. Ideally, the trade should happen whenever the buyer's value for the item exceeds the seller's cost. However, the classical resul…