Publications (58)
Sampling Multiple Edges Efficiently
Talya Eden, Saleet Mossel, Ronitt Rubinfeld
We present a sublinear time algorithm that allows one to sample multiple edges from a distribution that is pointwise -close to the uniform distribution, in an \emph{amortized-e…
A Fast Coloring Oracle for Average Case Hypergraphs
Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld +2
Hypergraph -colorability is one of the classical NP-hard problems. Person and Schacht [SODA'09] designed a deterministic algorithm whose expected running time is polynomial over…
Local Computation Algorithms for Graphs of Non-Constant Degrees
Reut Levi, Ronitt Rubinfeld, Anak Yodpinyanee
In the model of \emph{local computation algorithms} (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. Many recent…
Stochastic Matching via In-n-Out Local Computation Algorithms
Amir Azarmehr, Soheil Behnezhad, Alma Ghafari +1
Consider the following stochastic matching problem. Given a graph , an unknown subgraph is realized where includes every edge of independently…
A Local Algorithm for Constructing Spanners in Minor-Free Graphs
Reut Levi, Dana Ron, Ronitt Rubinfeld
Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider this problem in the setting of local algorithms: one wants to quickly determine…
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…