5 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…
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…
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…