# How Hard is Counting Triangles in the Streaming Model

arXiv: https://arxiv.org/abs/1304.1458 · HTML: https://mlsanity.com/paper/1304.1458/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Apr 2013.

## Built on by (most cited first, 1 of 1)

- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)

## Abstract (arXiv)

The problem of (approximately) counting the number of triangles in a graph is one of the basic problems in graph theory. In this paper we study the problem in the streaming model. We study the amount of memory required by a randomized algorithm to solve this problem. In case the algorithm is allowed one pass over the stream, we present a best possible lower bound of Omega(m) for graphs G with m edges on n vertices. If a constant number of passes is allowed, we show a lower bound of Omega(m/T), T the number of triangles. We match, in some sense, this lower bound with a 2-pass O(m/T1/3)-memory algorithm that solves the problem of distinguishing graphs with no triangles from graphs with at least T triangles. We present a new graph parameter ρ(G) -- the triangle density, and conjecture that the space complexity of the triangles problem is Omega(m/ρ(G)). We match this by a second algorithm that solves the distinguishing problem using O(m/ρ(G))-memory.