From the 1 of 14 linked papers with an AI index.
14 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…
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
The paper presents an algorithm that colors k‑colorable graphs in expected O(nk) time, breaking the long‑standing quadratic average‑case barrier and achieving linear time for const…
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…
Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
Slobodan MitroviÄ, Srikkanth Ramachandran, Ronitt Rubinfeld +1
In this work, we focus on designing an efficient Local Computation Algorithm (LCA) for the set cover problem, which is a core optimization task. The state-of-the-art LCA for comput…