54 citations · 138 across the 46 of their papers we have counts for
58 papers
Streaming Algorithms for Monotonicity Testing
Amir Azarmehr, Soheil Behnezhad, Lily Chung +3
Consider a poset - or equivalently an -vertex DAG - and a boolean function on its vertex set. We say is monotone if f…
Graph Spectral Sparsification is in Catalytic Logspace
Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld
We give a catalytic logspace algorithm for the problem of graph spectral sparsification. Given an undirected graph on vertices and , our algorithm outputs an…
Quality Control Algorithms for Pattern Counting
Cassandra Marcussen, Ronitt Rubinfeld, Madhu Sudan
In recent work, Marcussen, Rubinfeld, and Sudan introduced the notion of quality control problems, which aim to capture the task of determining if a given input is truly random. Fo…
Graph k-Coloring in Average Sublinear Time
Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld +2
Graph -coloring is one of the classic NP-complete problems. Previous work has studied its average time complexity, defined to be the average runtime of computing a -coloring…
Testing Unate Distributions
Daeho Lee, Shivam Nadimpalli, Mingda Qiao +1
We initiate the study of *unate distributions* over -- a natural analogue of unate Boolean functions -- by considering two basic testing problems that parallel well-st…
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…