8 citations · 12 across the 6 of their papers we have counts for
12 papers
Sampling an Edge in Sublinear Time Exactly and Optimally
Talya Eden, Shyam Narayanan, Jakub Tětek
Sampling edges from a graph in sublinear time is a fundamental problem and a powerful subroutine for designing sublinear-time algorithms. Suppose we have access to the vertices of…
Triangle and Four Cycle Counting with Predictions in Graph Streams
Justin Y. Chen, Talya Eden, Piotr Indyk +7
We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles, two fundamental problems in graph analytics that are widely studied in…
Approximating the Arboricity in Sublinear Time
Talya Eden, Saleet Mossel, Dana Ron
We consider the problem of approximating the arboricity of a graph , which we denote by , in sublinear time, where the arboricity of a graph is the minim…
Sampling Multiple Nodes in Large Networks: Beyond Random Walks
Omri Ben-Eliezer, Talya Eden, Joel Oren +1
Sampling random nodes is a fundamental algorithmic primitive in the analysis of massive networks, with many modern graph mining algorithms critically relying on it. We consider the…
Adversarially Robust Streaming via Dense--Sparse Trade-offs
Omri Ben-Eliezer, Talya Eden, Krzysztof Onak
A streaming algorithm is adversarially robust if it is guaranteed to perform correctly even in the presence of an adaptive adversary. Recently, several sophisticated frameworks for…
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…