\(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
• Конспекты Дартмута