C. Seshadhri

activity

20082025

most citedThe impossibility of low rank representations for triangle-rich complex networks

49 citations · 287 across the 45 of their papers we have counts for

collaborators

Showing 2016Show all

3 papers · 1 filter

cs.SI2016

A Fast and Provable Method for Estimating Clique Counts Using Turán's Theorem

Shweta Jain, C. Seshadhri

Clique counts reveal important properties about the structure of massive graphs, especially social networks. The simple setting of just 3-cliques (triangles) has received much atte…

cs.DS2016★ 9 cited

A $O (n)$ Non-Adaptive Tester for Unateness

Deeparnab Chakrabarty, C. Seshadhri

Khot and Shinkar (RANDOM, 2016) recently describe an adaptive, $O (n lo g (n) / ε)$ -query tester for unateness of Boolean functions $f : {0, 1}^{n} \to {0, 1}$ . In this note we…

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

A Fast and Provable Method for Estimating Clique Counts Using Turán's Theorem

A O(n) Non-Adaptive Tester for Unateness

Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection

A $O (n)$ Non-Adaptive Tester for Unateness