291 citations · 445 across the 25 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2017
Edge Estimation with Independent Set Oracles
Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy +2
We study the task of estimating the number of edges in a graph with access to only an independent set oracle. Independent set queries draw motivation from group testing and have ap…
cs.DS2016
Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube
Paul Beame, Cyrus Rashtchian
We study distributed protocols for finding all pairs of similar vectors in a large dataset. Our results pertain to a variety of discrete metrics, and we give concrete instantiation…