$k$-связность графа. $(1 + \varepsilon)$-приближение для MST. $t$-спаннеры для $t$-приближения на кратчайшие пути. Число треугольников в графе. Коммуникационная сложность. Задачи INDEX, EQ, DISJ. Нижняя оценка на однопроходный MJRTY, $F_\infty$, $s$-$t$ связность через INDEX. $F_k$ через DISJ. EQ за $O(\log n)$ вероятностно. Детерминированный $F_0$ через EQ + нижняя оценка на детерминированный приближенный алгоритм через коды.

Источники:

• Communication Complexity, Eyal Kushilevitz, Noam Nisan, 1996 (книга)
• Reductions in Streaming Algorithms, with an Application to Counting Triangles in Graphs, Ziv Bar-Yossef, Ravi Kumar, D. Sivakumar, 2002
• Analyzing Graph Structure via Linear Measurements, Kook Jin Ahn, Sudipto Guha, Andrew McGregor, 2012
• Конспекты Дартмута