T. Eden

activity

20152026

most citedApproximately Counting Triangles in Sublinear Time

25 citations · 44 across the 17 of their papers we have counts for

collaborators

Showing 2016Show all

2 papers · 1 filter

cs.DS2016

Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

Eric Blais, Clément L. Canonne, Talya Eden +2

A function $f : {- 1, 1}^{n} \to {- 1, 1}$ is a $k$ -junta if it depends on at most $k$ of its variables. We consider the problem of tolerant testing of $k$ -juntas, where the test…

cs.DS2016★ 3 cited

Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection

Talya Eden, Dana Ron, C. Seshadhri

We revisit the classic problem of estimating the degree distribution moments of an undirected graph. Consider an undirected graph $G = (V, E)$ with $n$ vertices, and define (for $s >…