25 citations · 44 across the 17 of their papers we have counts for
6 papers · 1 filter
Embeddings and labeling schemes for A*
Talya Eden, Piotr Indyk, Haike Xu
A* is a classic and popular method for graphs search and path finding. It assumes the existence of a heuristic function that estimates the shortest distance from any input…
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…
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…