City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Полупотоковые алгоритмы на графах и нижние оценки (ауд. 1008)
Streaming algorithms

What: Lecture
When: Friday, 26 February 2016, 17:00–18:30
Where: 2-й учебный корпус К(П)ФУ

Description

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

Attached files