5 papers · 1 filter
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…
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…
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…
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 queries. This is the first sublinear algorithm for this problem, which sh…
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…