3 papers
cs.DS2021
An Optimal Algorithm for Triangle Counting in the Stream
Rajesh Jayaram, John Kallaugher
We present a new algorithm for approximating the number of triangles in a graph whose edges arrive as an arbitrary order stream. If is the number of edges in , the n…
cs.DS2019
Separations and Equivalences between Turnstile Streaming and Linear Sketching
John Kallaugher, Eric Price
A longstanding observation, which was partially proven in \cite{LNW14,AHLW16}, is that any turnstile streaming algorithm can be implemented as a linear sketch (the reverse is trivi…
cs.DS2018
The Sketching Complexity of Graph and Hypergraph Counting
John Kallaugher, Michael Kapralov, Eric Price
Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database pr…