54 citations · 104 across the 31 of their papers we have counts for
6 papers · 1 filter
No Price Tags? No Problem: Query Strategies for Unpriced Information
Shivam Nadimpalli, Mingda Qiao, Ronitt Rubinfeld
The classic *priced query model*, introduced by Charikar et al. (STOC 2000), captures the task of computing a known function on an unknown input when each input variable can only b…
Testable algorithms for approximately counting edges and triangles in sublinear time and space
Talya Eden, Ronitt Rubinfeld, Arsen Vasilyan
We consider the fundamental problems of approximately counting the numbers of edges and triangles in a graph in sublinear time. Previous algorithms for these tasks are significantl…
Quality control in sublinear time: a case study via random graphs
Cassandra Marcussen, Ronitt Rubinfeld, Madhu Sudan
Many algorithms are designed to work well on average over inputs. When running such an algorithm on an arbitrary input, we must ask: Can we trust the algorithm on this input? We id…
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…
Better Private Distribution Testing by Leveraging Unverified Auxiliary Data
Maryam Aliakbarpour, Arnav Burudgunte, Clément Cannone +1
We extend the framework of augmented distribution testing (Aliakbarpour, Indyk, Rubinfeld, and Silwal, NeurIPS 2024) to the differentially private setting. This captures scenarios…
Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
Talya Eden, Reut Levi, Dana Ron +1
Counting small subgraphs, referred to as motifs, in large graphs is a fundamental task in graph analysis, extensively studied across various contexts and computational models. In t…