Сложность вычислений

Communication Complexity

HyperLogLog считает уникальных посетителей сайта в 12 килобайтах памяти с погрешностью 1.6%. Точный алгоритм требует гигабайты. Почему нельзя сделать точно и дёшево? Ответ - в нижних оценках коммуникационной сложности.

**Apache Kafka / Flink:** streaming-обработка больших данных ограничена памятью - коммуникационная сложность объясняет почему приближённые алгоритмы неизбежны
**VLSI design:** нижние оценки коммуникации дают нижние оценки на количество проводников между частями чипа
**Distributed computing:** нижние оценки на синхронизацию в MapReduce и Spark выводятся из коммуникационной сложности

Протоколы коммуникации

Алиса знает число x ∈ {0,1}^n, Боб знает y ∈ {0,1}^n. Они хотят вычислить f(x, y) - например, проверить x = y или найти x AND y. Вычислительная мощь неограничена - их единственный ресурс это **биты коммуникации**. Сколько битов надо передать в худшем случае?

Протокол - дерево разговора. В каждом узле один из игроков посылает бит, зависящий только от своего входа и ранее принятых битов. Лист дерева - результат f(x, y). **Сложность протокола** = глубина дерева = число раундов = количество переданных битов.

**Классы сложности:** D(f) - детерминированная, R(f) - рандомизированная (публичные монеты), N(f) - недетерминированная. Всегда: log(rank(M_f)) ≤ D(f) ≤ rank(M_f), где M_f - матрица функции.

Алиса и Боб хотят проверить DISJOINTNESS: пересекаются ли множества A и B ⊆ [n]? Какова детерминированная сложность?

Нижние оценки

Как доказать, что задача требует много коммуникации? Прямой перебор всех протоколов невозможен. Нужны методы, позволяющие ограничить снизу любой протокол, даже неизвестный нам.

**Fooling set (обманывающее множество):** набор пар {(x_i, y_i)} такой, что f(x_i, y_i) = 1 для всех i, но для i ≠ j: f(x_i, y_j) = 0 или f(x_j, y_i) = 0. Если такой набор из S пар существует, то D(f) ≥ log_2 S.

**Нижние оценки через коммуникацию** - один из немногих известных методов получения нижних оценок в реальных моделях вычисления. Они используются для доказательства нижних оценок в схемах, потоковых алгоритмах и VLSI.

Fooling set для функции f имеет размер S = 2^{n/2}. Что можно вывести?

Matrix Rank Method

Функции f: {0,1}^n × {0,1}^n → {0,1} соответствует матрица M_f размера 2^n × 2^n, где M_f[x][y] = f(x, y). Ранг этой матрицы над полем (обычно над вещественными числами или GF(2)) напрямую связан с коммуникационной сложностью.

**Теорема (Mehlhorn-Schmidt 1982):** D(f) ≥ log_2(rank(M_f)). Это следует из того, что каждый детерминированный протокол на k битах разбивает матрицу на 2^k монохроматических прямоугольников - а такое покрытие возможно только если ранг матрицы не превышает 2^k.

**Log rank conjecture (Lovász-Saks 1988):** D(f) = O((log rank(M_f))^c) для некоторой константы c? Это одна из главных открытых проблем коммуникационной сложности. Лучший известный результат: D(f) = O(rank^{0.5} · log rank).

Матрица функции f имеет ранг r. Что следует из Matrix Rank Method?

Применение в streaming

Нижние оценки коммуникационной сложности переносятся в streaming-алгоритмы через прямую редукцию. Алиса кодирует x в состояние потокового алгоритма после обработки первой половины потока, Боб симулирует алгоритм на второй половине. Если алгоритм использует m битов памяти - это m-битное сообщение от Алисы к Бобу.

**Нижние оценки для frequency moments:** поток из n элементов, нужно вычислить F_k = Σ f_i^k, где f_i - частота элемента i. Алиса и Боб делят поток: каждый нижний предел на память streaming-алгоритма = нижний предел на коммуникацию соответствующей задачи.

**Практическое следствие:** именно поэтому HyperLogLog, Count-Min Sketch, Bloom Filters - все они приближённые. Точные алгоритмы для этих задач требуют линейной памяти - доказано через коммуникационную сложность.

Почему нижние оценки коммуникационной сложности дают нижние оценки для streaming-алгоритмов?