54 citations · 104 across the 31 of their papers we have counts for
3 papers · 1 filter
Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time
Amartya Shankha Biswas, Talya Eden, Ronitt Rubinfeld
We consider the problem of sampling and approximately counting an arbitrary given motif in a graph , where access to is given via queries: degree, neighbor, and pair, as…
Learning-based Support Estimation in Sublinear Time
Talya Eden, Piotr Indyk, Shyam Narayanan +3
We consider the problem of estimating the number of distinct elements in a large data set (or, equivalently, the support size of the distribution induced by the data set) from a ra…
Local Access to Random Walks
Amartya Shankha Biswas, Edward Pyne, Ronitt Rubinfeld
For a graph on vertices, naively sampling the position of a random walk of at time requires work . We desire local access algorithms supporting $\text{position}(G…