25 citations · 44 across the 17 of their papers we have counts for
30 papers
A note on approximating the average degree of bounded arboricity graphs
Talya Eden, C. Seshadhri
Estimating the average degree of graph is a classic problem in sublinear graph algorithm. Eden, Ron, and Seshadhri (ICALP 2017, SIDMA 2019) gave a simple algorithm for this problem…
Fast Agnostic Learners in the Plane
Talya Eden, Ludmila Glinskih, Sofya Raskhodnikova
We investigate the computational efficiency of agnostic learning for several fundamental geometric concept classes in the plane. While the sample complexity of agnostic learning is…
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…
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…
A Sublinear Algorithm for Approximate Shortest Paths in Large Networks
Sabyasachi Basu, Nadia Kōshima, Talya Eden +2
Computing distances and finding shortest paths in massive real-world networks is a fundamental algorithmic task in network analysis. There are two main approaches to solving this t…
Plant-and-Steal: Truthful Fair Allocations via Predictions
Ilan Reuven Cohen, Alon Eden, Talya Eden +1
We study truthful mechanisms for approximating the Maximin-Share (MMS) allocation of agents with additive valuations for indivisible goods. Algorithmically, constant factor approxi…
Testing -freeness in bounded-arboricity graphs
Talya Eden, Reut Levi, Dana Ron
We study the problem of testing -freeness (-cycle-freeness) for fixed constant in graphs with bounded arboricity (but unbounded degrees). In particular, we are inte…
Triangle Counting with Local Edge Differential Privacy
Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova +1
Many deployments of differential privacy in industry are in the local model, where each party releases its private information via a differentially private randomizer. We study tri…
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…
Bias Reduction for Sum Estimation
Talya Eden, Jakob Bæk Tejs Houen, Shyam Narayanan +2
In classical statistics and distribution testing, it is often assumed that elements can be sampled from some distribution , and that when an element is sampled, the probabil…
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…
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…
Almost Optimal Bounds for Sublinear-Time Sampling of -Cliques: Sampling Cliques is Harder Than Counting
Talya Eden, Dana Ron, Will Rosenbaum
In this work, we consider the problem of sampling a -clique in a graph from an almost uniform distribution in sublinear time in the general graph query model. Specifically the a…
Sampling Multiple Edges Efficiently
Talya Eden, Saleet Mossel, Ronitt Rubinfeld
We present a sublinear time algorithm that allows one to sample multiple edges from a distribution that is pointwise -close to the uniform distribution, in an \emph{amortized-ef…
Massively Parallel Algorithms for Small Subgraph Counting
Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu +2
Over the last two decades, frameworks for distributed-memory parallel computation, such as MapReduce, Hadoop, Spark and Dryad, have gained significant popularity with the growing p…
The Arboricity Captures the Complexity of Sampling Edges
Talya Eden, Dana Ron, Will Rosenbaum
In this paper, we revisit the problem of sampling edges in an unknown graph from a distribution that is (pointwise) almost uniform over . We consider the case where…
Faster sublinear approximations of -cliques for low arboricity graphs
Talya Eden, Dana Ron, C. Seshadhri
Given query access to an undirected graph , we consider the problem of computing a -approximation of the number of -cliques in . The standard query model for gene…
Provable and practical approximations for the degree distribution using sublinear graph samples
Talya Eden, Shweta Jain, Ali Pinar +2
The degree distribution is one of the most fundamental properties used in the analysis of massive graphs. There is a large literature on graph sampling, where the goal is to estima…
Lower Bounds for Approximating Graph Parameters via Communication Complexity
Talya Eden, Will Rosenbaum
In a celebrated work, Blais, Brody, and Matulef developed a technique for proving property testing lower bounds via reductions from communication complexity. Their work focused on…