Сложность связи

В информатике теоретической сложность коммуникации изучает объем коммуникации, необходимый для решения проблемы, когда входные данные распределяются между двумя или более сторонами. Исследование сложности связи было впервые предложено Эндрю Яо в 1979 году при изучении проблемы вычислений, распределенных между несколькими машинами. ^[1]Задача обычно формулируется следующим образом: каждая из двух сторон (традиционно называемых Алисой и Бобом ) получает (потенциально разные) $n$ - битовая строка $x$ и $y$ . Цель состоит в том, чтобы Алиса вычислила значение определенной функции. $f(x,y)$ , это зависит от обоих $x$ и $y$ , с наименьшим количеством связи между ними.

Хотя Алиса и Боб всегда могут добиться успеха, если Боб отправит всю свою $n$ -битовая строка Алисе (которая затем вычисляет функцию $f$ ), идея здесь состоит в том, чтобы найти умные способы расчета $f$ с менее чем $n$ кусочки общения. Обратите внимание, что, в отличие от теории сложности вычислений , сложность связи не связана с объемом вычислений, выполняемых Алисой или Бобом, или размером используемой памяти , поскольку мы обычно ничего не предполагаем о вычислительной мощности Алисы или Боба.

Эта абстрактная проблема с двумя сторонами (называемая сложностью двустороннего общения) и ее общая форма с более чем двумя сторонами актуальна во многих контекстах. Например, при проектировании схем СБИС стремятся минимизировать потребляемую энергию за счет уменьшения количества электрических сигналов, передаваемых между различными компонентами во время распределенных вычислений. Проблема актуальна также при исследовании структур данных и оптимизации компьютерных сетей. Обзоры этой области см. в учебниках Рао и Иегудайофф (2020) и Кушилевица и Нисана (2006) .

Формальное определение

Позволять $f:X\times Y\rightarrow Z$ где мы предполагаем в типичном случае, что $X=Y=\{0,1\}^{n}$ и $Z=\{0,1\}$ . Алиса держит $n$ -битовая строка $x\in X$ пока Боб держит $n$ -битовая строка $y\in Y$ . Обмениваясь друг с другом побитно ( приняв некоторый протокол связи ), Алиса и Боб желают вычислить значение заранее согласованный $f(x,y)$ так, что по крайней мере одна сторона знает значение в конце сообщения. На этом этапе ответ может быть передан обратно, так что за счет одного дополнительного бита обе стороны узнают ответ. Наихудшая сложность связи в этой коммуникационной задаче вычислений. $f$ , обозначенный как $D(f)$ , тогда определяется как

D(f)=

минимальное количество битов, которыми обмениваются Алиса и Боб в худшем случае.

Как отмечалось выше, для любой функции $f:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}$ , у нас есть $D(f)\leq n$ .Используя приведенное выше определение, полезно подумать о функции $f$ как матрица $A$ (называемая входной матрицей или матрицей связи ), где строки индексируются $x\in X$ и столбцы по $y\in Y$ . Элементами матрицы являются $A_{x,y}=f(x,y)$ . Изначально и у Алисы, и у Боба есть копия всей матрицы. $A$ (предполагая, что функция $f$ известно обеим сторонам). Тогда задачу вычисления значения функции можно перефразировать как «обнуление» соответствующего элемента матрицы. Эту проблему можно решить, если Алиса или Боб знают оба $x$ и $y$ . В начале связи количество вариантов значения функции на входах равно размеру матрицы, т.е. $2^{2n}$ . Затем, когда каждая сторона немного общается с другой, количество вариантов ответа уменьшается, поскольку это исключает набор строк/столбцов, в результате чего подматрица образуется $A$ .

Более формально, набор $R\subseteq X\times Y$ называется (комбинаторным) прямоугольником, если всякий раз, когда $(x_{1},y_{1})\in R$ и $(x_{2},y_{2})\in R$ затем $(x_{1},y_{2})\in R$ . Эквивалентно, $R$ является комбинаторным прямоугольником, если его можно выразить как $R=M\times N$ для некоторых $M\subseteq X$ и $N\subseteq Y$ . Рассмотрим случай, когда $k$ биты уже обмениваются между сторонами. Теперь для конкретного $h\in \{0,1\}^{k}$ , определим матрицу

T_{h}=\{(x,y):{\text{ the }}k{\text{-bits exchanged on input }}(x,y){\text{ is }}h\}

Затем, $T_{h}\subseteq X\times Y$ , и нетрудно показать, что $T_{h}$ представляет собой комбинаторный прямоугольник в $A$ .

Пример: эквалайзер

Мы рассматриваем случай, когда Алиса и Боб пытаются определить, равны ли их входные строки. Формально определим функцию равенства , обозначим $EQ:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}$ , к $EQ(x,y)=1$ если $x=y$ . Как мы покажем ниже, любое детерминированное решение протокола связи $EQ$ требует $n$ биты общения в худшем случае. В качестве разминочного примера рассмотрим простой случай: $x,y\in \{0,1\}^{3}$ . Функция равенства в этом случае может быть представлена матрицей ниже. В строках представлены все возможности $x$ , столбцы $y$ .

эквалайзер	000	001	010	011	100	101	110	111
000	1	0	0	0	0	0	0	0
001	0	1	0	0	0	0	0	0
010	0	0	1	0	0	0	0	0
011	0	0	0	1	0	0	0	0
100	0	0	0	0	1	0	0	0
101	0	0	0	0	0	1	0	0
110	0	0	0	0	0	0	1	0
111	0	0	0	0	0	0	0	1

В этой таблице функция оценивается как 1 только тогда, когда $x$ равно $y$ (т.е. по диагонали). Также довольно легко увидеть, как передача одного бита делит чьи-то возможности пополам. Когда первый бит $y$ равно 1, рассмотрим только половину столбцов (где $y$ может равняться 100, 101, 110 или 111).

Теорема: D(EQ) = n

Доказательство. Предположим, что $D(EQ)\leq n-1$ . Это означает, что существует $x\neq x'$ такой, что $(x,x)$ и $(x',x')$ иметь одинаковую стенограмму общения $h$ . Поскольку этот транскрипт определяет прямоугольник, $f(x,x')$ также должно быть 1. По определению $x\neq x'$ и мы знаем, что равенство справедливо только для $(a,b)$ когда $a=b$ . Это приводит к противоречию.

Этот метод доказательства нижних границ детерминированной связи называется методом обманывающего множества . ^[2]

Рандомизированная сложность общения

В приведенном выше определении нас интересует количество битов, которые должны быть детерминированно переданы между двумя сторонами. Если обеим сторонам предоставлен доступ к генератору случайных чисел, смогут ли они определить значение $f$ при гораздо меньшем объеме обмена информацией? Яо в своей основополагающей статье ^[1]отвечает на этот вопрос, определяя рандомизированную сложность коммуникации.

Рандомизированный протокол $R$ для функции $f$ имеет двустороннюю ошибку.

\Pr[R(x,y)=0]>{\frac {2}{3}},{\textrm {if}}\,f(x,y)=0

\Pr[R(x,y)=1]>{\frac {2}{3}},{\textrm {if}}\,f(x,y)=1

Рандомизированный протокол — это детерминированный протокол, который использует дополнительную случайную строку в дополнение к обычному вводу. Для этого есть две модели: общедоступная строка — это случайная строка, заранее известная обеим сторонам, а частная строка генерируется одной стороной и должна быть передана другой стороне. Теорема, представленная ниже, показывает, что любой общедоступный строковый протокол может быть смоделирован с помощью частного строкового протокола, который использует O(log n) дополнительных битов по сравнению с оригиналом.

Обратите внимание, что в приведенных выше вероятностных неравенствах считается, что результат протокола зависит только от случайной строки; обе строки x и y остаются фиксированными. Другими словами, если R ( x , y ) дает g ( x , y , r ) при использовании случайной строки r , то g ( x , y , r ) = f ( x , y ) по крайней мере для 2/3 всех варианты для строки r .

Рандомизированная сложность определяется просто как количество битов, которыми обмениваются в таком протоколе.

Обратите внимание, что также возможно определить рандомизированный протокол с односторонней ошибкой, и сложность определяется аналогично.

Пример: эквалайзер

Возвращаясь к предыдущему примеру EQ , если уверенность не требуется, Алиса и Боб могут проверить равенство, используя только ⁠ $O(\log n)$ ⁠ сообщения. Рассмотрим следующий протокол: предположим, что Алиса и Боб имеют доступ к одной и той же случайной строке. $z\in \{0,1\}^{n}$ . Алиса вычисляет $z\cdot x$ и отправляет этот бит (назовем его b ) Бобу. ( $(\cdot )$ является скалярным произведением в GF(2) .) Затем Боб сравнивает b с $z\cdot y$ . Если они одинаковы, Боб соглашается, говоря, что x равно y . В противном случае он отвергает.

Ясно, что если $x=y$ , затем $z\cdot x=z\cdot y$ , так $Prob_{z}[Accept]=1$ . Если x не равно y , все равно возможно, что $z\cdot x=z\cdot y$ , что дало бы Бобу неверный ответ. Как это происходит?

Если x и y не равны, они должны отличаться в некоторых местах:

{\begin{cases}x=c_{1}c_{2}\ldots p\ldots p'\ldots x_{n}\\y=c_{1}c_{2}\ldots q\ldots q'\ldots y_{n}\\z=z_{1}z_{2}\ldots z_{i}\ldots z_{j}\ldots z_{n}\end{cases}}

Если $x$ и $y$ совпадают, $z_{i}*x_{i}=z_{i}*c_{i}=z_{i}*y_{i}$ поэтому эти термины одинаково влияют на скалярные произведения. Мы можем спокойно игнорировать эти термины и смотреть только на то, где $x$ и $y$ отличаются. Кроме того, мы можем поменять местами биты $x_{i}$ и $y_{i}$ без изменения того, равны ли скалярные произведения. Это означает, что мы можем поменять местами биты так, чтобы $x$ содержал только нули, а $y$ — только единицы:

{\begin{cases}x'=00\ldots 0\\y'=11\ldots 1\\z'=z_{1}z_{2}\ldots z_{n'}\end{cases}}

Обратите внимание, что $z'\cdot x'=0$ и $z'\cdot y'=\Sigma _{i}z'_{i}$ . Теперь возникает вопрос: для некоторой случайной строки $z'$ , какова вероятность того, что $\Sigma _{i}z'_{i}=0$ ? Поскольку каждый $z'_{i}$ с равной вероятностью будет 0 или 1 , эта вероятность просто $1/2$ . Таким образом, когда $x$ не равен $y$ , $Prob_{z}[Accept]=1/2$ . Алгоритм можно повторять многократно, чтобы повысить его точность. Это соответствует требованиям к алгоритму рандомизированной связи.

Это показывает, что если Алиса и Боб совместно используют случайную строку длины n , они могут отправить один бит друг другу для вычисления. $EQ(x,y)$ . В следующем разделе показано, что Алиса и Боб могут обмениваться только ⁠ $O(\log n)$ ⁠ биты, которые так же хороши, как совместное использование случайной строки длины n . Как только это будет показано, из этого следует, что EQ можно вычислить в ⁠ $O(\log n)$ ⁠ сообщения.

Пример: ГХ

В качестве еще одного примера рандомизированной сложности коммуникации мы обратимся к примеру, известному как проблема пробела-Хемминга (сокращенно GH ). Формально и Алиса, и Боб поддерживают двоичные сообщения. $x,y\in \{-1,+1\}^{n}$ и хотел бы определить, очень ли похожи строки или не очень похожи. В частности, они хотели бы найти протокол связи, требующий передачи как можно меньшего количества битов для вычисления следующей частичной булевой функции:

{\text{GH}}_{n}(x,y):={\begin{cases}-1&\langle x,y\rangle \leq {\sqrt {n}}\\+1&\langle x,y\rangle \geq {\sqrt {n}}.\end{cases}}

Очевидно, что они должны передавать все свои биты, если протокол должен быть детерминированным (это потому, что если существует детерминированное, строгое подмножество индексов, которые Алиса и Боб передают друг другу, то представьте, что у вас есть пара строк, которые в этом наборе не согласен в ${\sqrt {n}}-1$ позиции. Если в какой-либо позиции, которая не ретранслируется, возникает другое разногласие, то это влияет на результат ${\text{GH}}_{n}(x,y)$ , и, следовательно, приведет к неправильной процедуре.

Тогда возникает естественный вопрос: разрешено ли нам ошибаться? $1/3$ времени (в случайных случаях $x,y$ вытянуты равномерно случайным образом из $\{-1,+1\}^{n}$ ), тогда можем ли мы обойтись протоколом с меньшим количеством битов? Оказывается, что ответ несколько неожиданный — нет, благодаря результату Чакрабарти и Регева в 2012 году: они показывают, что для случайных случаев любая процедура, которая, по крайней мере, правильна $2/3$ времени необходимо отправить $\Omega (n)$ битов общения, то есть, по сути, всех из них.

Публичные монеты против частных монет

Создание случайных протоколов становится проще, когда обе стороны имеют доступ к одной и той же случайной строке, известной как протокол общей строки. Однако даже в тех случаях, когда две стороны не используют общую случайную строку, все равно можно использовать протоколы частных строк с небольшими затратами на связь. Любой протокол случайных чисел с общей строкой, использующий любое количество случайных строк, может быть смоделирован протоколом частных строк, который использует дополнительные биты O(log n) .

Интуитивно мы можем найти некоторый набор строк, в котором достаточно случайности, чтобы запустить случайный протокол с небольшим увеличением ошибки. Этот набор может быть общим заранее, и вместо того, чтобы рисовать случайную строку, Алисе и Бобу нужно только договориться, какую строку выбрать из общего набора. Этот набор достаточно мал, чтобы можно было эффективно сообщить о выборе. Далее следует формальное доказательство.

Рассмотрим некоторый случайный протокол P с максимальной частотой ошибок 0,1. Позволять $R$ быть $100n$ строки длины n , пронумерованные $r_{1},r_{2},\dots ,r_{100n}$ . Учитывая такое $R$ , определить новый протокол $P'_{R}$ который случайным образом выбирает некоторые $r_{i}$ а затем запускает P , используя $r_{i}$ как общую случайную строку. требуется O (log 100 n ) = O (log n ) битов. Чтобы сообщить о выборе, $r_{i}$ .

Давайте определим $p(x,y)$ и $p'_{R}(x,y)$ быть вероятностью того, что $P$ и $P'_{R}$ вычислить правильное значение для ввода $(x,y)$ .

Для фиксированной $(x,y)$ , мы можем использовать неравенство Хёффдинга, чтобы получить следующее уравнение:

\Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq 2\exp(-2(0.1)^{2}\cdot 100n)<2^{-2n}

Таким образом, когда у нас нет $(x,y)$ зафиксированный:

\Pr _{R}[\exists (x,y):\ |p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq \sum _{(x,y)}\Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]<\sum _{(x,y)}2^{-2n}=1

Последнее равенство, приведенное выше, справедливо, поскольку существуют $2^{2n}$ разные пары $(x,y)$ . Поскольку вероятность не равна 1, существует некоторый $R_{0}$ так что для всех $(x,y)$ :

|p'_{R_{0}}(x,y)-p(x,y)|<0.1

С $P$ имеет не более 0,1 вероятности ошибки, $P'_{R_{0}}$ может иметь не более 0,2 вероятности ошибки.

Коллапс рандомизированной сложности общения

Допустим, мы дополнительно разрешаем Алисе и Бобу совместно использовать какой-то ресурс, например пару запутанных частиц. Используя этот ресурс, Алиса и Боб могут сопоставить свою информацию и, таким образом, попытаться «свернуть» (или «упрощать») сложность коммуникации в следующем смысле.

Определение. Ресурс $R$ называется «разрушающимся» , если при использовании этого ресурса $R$ , только одного бита классической коммуникации достаточно, чтобы Алиса узнала оценку $f(x,y)$ в худшем случае для любой логической функции $f$ .

Удивительным фактом коллапса сложности коммуникации является то, что функция $f$ может иметь сколь угодно большой размер записи, но при этом количество битов связи остается постоянным и равным одному.

Показано, что некоторые ресурсы не схлопываются, например квантовые корреляции. ^[3] или, в более общем смысле, почти квантовые корреляции, ^[4] тогда как, наоборот, показано, что некоторые другие ресурсы разрушают рандомизированную сложность коммуникации, например PR-бокс, ^[5] или несколько шумных PR-боксов, удовлетворяющих некоторым условиям. ^[6]^[7]^[8]

Сложность распределения

Один из подходов к изучению сложности рандомизированной коммуникации – это сложность распределения.

При совместном распределении $\mu$ на входах обоих игроков соответствующая сложность распределения функции $f$ — минимальная стоимость детерминированного протокола $R$ такой, что $\Pr[f(x,y)=R(x,y)]\geq 2/3$ , где входные данные выбираются в соответствии с $\mu$ .

Принцип минимакса Яо ^[9] (частный случай фон Неймана ) минимаксной теоремы утверждает, что рандомизированная коммуникационная сложность функции равна ее максимальной сложности распределения, где максимум берется по всем совместным распределениям входных данных (не обязательно распределениям продуктов!).

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

В качестве примера рассмотрим функцию непересекаемости DISJ: каждый из входов интерпретируется как подмножество $\{1,\dots ,n\}$ и DISJ( $x$ , $y$ )=1, если два набора не пересекаются. Разборов ^[10] оказался $\Omega (n)$ нижнюю границу сложности рандомизированной коммуникации, рассматривая следующее распределение: с вероятностью 3/4 выбрать два случайных непересекающихся набора размера $n/4$ , и с вероятностью 1/4 выберем два случайных набора размера $n/4$ с уникальным перекрестком.

Информационная сложность

Мощным подходом к изучению сложности распределения является информационная сложность. По инициативе Бар-Йосефа, Джайрама, Кумара и Сивакумара, ^[11] этот подход был систематизирован в работах Барака, Бравермана, Чена и Рао. ^[12] и Браверман и Рао. ^[13]

(Внутренняя) информационная сложность (возможно, рандомизированного) протокола $R$ относительно распределения $µ$ определяется следующим образом. Позволять $(X,Y)\sim \mu$ будут случайными входными данными, выбранными в соответствии с $µ$ , и пусть $Π$ будет транскриптом $R$ при запуске на входах $X,Y$ . Информационная сложность протокола

\operatorname {IC} _{\mu }(R)=I(\Pi ;Y|X)+I(\Pi ;X|Y),

где $I$ обозначает условную взаимную информацию .Первое слагаемое измеряет объем информации, которую Алиса узнает о вводе Боба из стенограммы, а второе измеряет объем информации, который Боб узнает о вводе Алисы.

Информационная $сложность ε$ -ошибки функции $f$ относительно распределения $µ$ — это минимальная информационная сложность протокола для $f$ , ошибка которого (относительно $µ$ ) не превосходит $ε$ .

Браверман и Рао доказали, что информация — это амортизированное общение. Это означает, что стоимость решения $n$ независимых копий $f$ примерно $в n$ раз превышает информационную сложность $f$ . Это аналогично хорошо известной интерпретации энтропии Шеннона как амортизированной длины в битах, необходимой для передачи данных из данного источника информации. В доказательстве Бравермана и Рао используется метод, известный как «сжатие протокола», при котором протокол, эффективный для информации, «сжимается» в протокол, эффективный для связи.

Методы информационной сложности позволяют вычислить точную (вплоть до первого порядка) коммуникативную сложность непересекающихся множеств. $1.4923\ldots n$ . ^[14]

Методы информационной сложности также использовались для анализа расширенных формулировок, доказывая по существу оптимальную нижнюю границу сложности алгоритмов, основанных на линейном программировании , которые приближенно решают задачу максимальной клики . ^[15]

Опрос Омри Вайнштейна в 2015 году ^[16] обследует предмет.

Сложность квантовой связи

Сложность квантовой связи пытается количественно оценить возможное сокращение связи за счет использования квантовых эффектов во время распределенных вычислений.

Было предложено по крайней мере три квантовых обобщения сложности коммуникации; обзор см. в предложенном тексте Г. Брассара.

Первая — это модель кубитной связи , где стороны могут использовать квантовую связь вместо классической связи, например, путем обмена фотонами через оптическое волокно .

Во второй модели связь по-прежнему осуществляется с помощью классических битов, но сторонам разрешено манипулировать неограниченным количеством квантово-запутанных состояний в рамках своих протоколов. Выполняя измерения запутанных состояний, стороны могут сэкономить на классической коммуникации во время распределенных вычислений.

Третья модель предполагает доступ к ранее общей запутанности в дополнение к связи кубитов и является наименее изученной из трех квантовых моделей.

Недетерминированная сложность связи

При недетерминированной сложности связи Алиса и Боб имеют доступ к оракулу. После получения слова оракула стороны общаются, чтобы сделать вывод. $f(x,y)$ . Тогда недетерминированная сложность связи будет максимальной по всем парам. $(x,y)$ по сумме количества битов, которыми обмениваются, и длины кодирования слова оракула.

С другой стороны, это равносильно покрытию всех 1-элементов 0/1-матрицы комбинаторными 1-прямоугольниками (т. е. несмежными, невыпуклыми подматрицами, все элементы которых равны единице (см. Кушилевиц и Нисан или Дитцфельбингер и др. )). Недетерминированная сложность связи представляет собой двоичный логарифм прямоугольника, покрывающего число матрицы: минимальное количество комбинаторных 1-прямоугольников, необходимое для покрытия всех 1-элементов матрицы, без покрытия каких-либо 0-элементов.

Недетерминированная сложность связи встречается как средство получения нижних оценок детерминированной сложности связи (см. Дитцфельбингер и др.), а также в теории неотрицательных матриц, где она дает нижнюю оценку неотрицательного ранга неотрицательной матрицы. ^[17]

Сложность связи с неограниченными ошибками

В режиме неограниченной ошибки Алиса и Боб имеют доступ к частной монете и своим собственным входам. $(x,y)$ . В этом случае Алиса добьется успеха, если ответит правильным значением $f(x,y)$ с вероятностью строго больше 1/2. Другими словами, если ответы Алисы имеют ненулевую корреляцию с истинным значением $f(x,y)$ , то протокол считается действительным.

Обратите внимание, что требование о том, чтобы монета была частной, является существенным. В частности, если количество общедоступных битов, разделяемых Алисой и Бобом, не учитывать в расчете сложности связи, легко утверждать, что вычисление любой функции имеет $O(1)$ сложность общения. ^[18] С другой стороны, обе модели эквивалентны, если количество общедоступных битов, используемых Алисой и Бобом, учитывается при общем объеме обмена данными протокола. ^[19]

Хотя и тонкие, нижние границы этой модели чрезвычайно сильны. Более конкретно, ясно, что любая граница для задач этого класса немедленно влечет за собой эквивалентные границы для проблем в детерминированной модели, а также в моделях частной и публичной монеты, но такие границы также немедленно выполняются для недетерминированных моделей связи и моделей квантовой связи. ^[20]

Форстер ^[21] был первым, кто доказал явные нижние оценки для этого класса, показав, что вычисление скалярного произведения $\langle x,y\rangle$ требуется как минимум $\Omega (n)$ бит связи, хотя более ранний результат Алона, Франкла и Рёдля доказал, что сложность связи почти для всех булевых функций $f:\{0,1\}^{n}\times \{0,1\}^{n}\to \{0,1\}$ является $\Omega (n)$ . ^[22]

Лифтинг

Лифтинг — это общий метод теории сложности , при котором нижняя граница простой меры сложности «поднимается» до нижней границы более сложной меры.

Эта техника была впервые использована Разом и Маккензи в контексте сложности коммуникации. ^[23] который доказал первую теорему о подъеме запроса на связь и использовал результат для разделения монотонной NC -иерархии.

Дана функция $f\colon \{0,1\}^{n}\to \{0,1\}$ и гаджет $g\colon \{0,1\}^{a}\times \{0,1\}^{b}\to \{0,1\}$ , их состав $f\circ g\colon \{0,1\}^{na}\times \{0,1\}^{nb}\to \{0,1\}$ определяется следующим образом:

(f\circ g)(x,y)=f(g(x_{1,1}\cdots x_{1,a},y_{1,1}\cdots y_{1,b}),\dots ,g(x_{n,1}\cdots x_{n,a},y_{n,1}\cdots y_{n,b})).

Другими словами, $x$ разделен на $n$ блоки длины $a$ , и $y$ разделен на $n$ блоки длины $b$ . Гаджет применяется $n$ раз на блоки, а выходные данные подаются в $f$ . Схематически:

На этой схеме каждый из входов $\mathbf {x} _{1},\dots ,\mathbf {x} _{n}$ имеет $длину в битах$ , и каждый из входов $\mathbf {y} _{1},\dots ,\mathbf {y} _{n}$ имеет $длину b$ бит.

дерево решений Глубинное $\Delta$ для $f$ может быть преобразовано в протокол связи, стоимость которого равна $\Delta \cdot D(g)$ : каждый раз, когда дерево запрашивает бит, соответствующее значение $g$ рассчитывается с использованием оптимального протокола для $g$ . Раз и Маккензи показали, что это оптимально с точностью до постоянного коэффициента, когда $g$ это так называемый «индексирующий гаджет», в котором $x$ имеет длину $c\log n$ (для достаточно большой константы $c$ ), $y$ имеет длину $n^{c}$ , и $g(x,y)$ это $x$ -й кусочек $y$ .

Доказательство подъемной теоремы Раза – Маккензи использует метод моделирования, в котором протокол для составной функции $f\circ g$ используется для создания дерева решений для $f$ . Гёос, Питасси и Ватсон ^[24] дал изложение оригинального доказательства. С тех пор в нескольких работах были доказаны аналогичные теоремы с различными гаджетами, такими как внутренний продукт. ^[25] Самый маленький гаджет, с которым можно работать, — это индексирующий гаджет с $c=1+\epsilon$ . ^[26]Гёос, Питасси и Уотсон распространили технику Раза-Маккензи на рандомизированные протоколы. ^[27]

Простая модификация теоремы о подъеме Раза – Маккензи дает нижнюю оценку $\Delta \cdot D(g)$ от логарифма размера дерева протоколов вычислений $f\circ g$ , где $\Delta$ – глубина оптимального дерева решений для $f$ . Гарг, Гёос, Камат и Соколов распространили это на настройку, подобную DAG , ^[28] и использовали свой результат для получения нижних границ монотонной схемы . Тот же метод нашел применение и для определения сложности доказательства . ^[29]

Другой тип подъема иллюстрируется методом паттерн-матрицы Шерстова: ^[30] что дает нижнюю оценку сложности квантовой связи $f\circ g$ , где $g$ — модифицированный индексирующий гаджет, выраженный в приблизительной степени $f$ . Приближенная степень булевой функции — это минимальная степень многочлена, который аппроксимирует функцию во всех логических точках с точностью до аддитивной ошибки 1/3.

В отличие от доказательства Раза–Маккензи, в котором используется метод моделирования, доказательство Шерстова использует двойное свидетельство для приблизительной степени $f$ и дает нижнюю оценку сложности квантового запроса $f\circ g$ используя метод обобщенной невязки . Двойной свидетель приближенной степени $f$ является свидетельством нижней границы приближенной степени, полученной с помощью двойственности ЛП . Этот двойной свидетель преобразуется в другие объекты, составляющие данные для метода обобщенного несоответствия.

Другим примером такого подхода является работа Питасси и Робере. ^[31] в котором алгебраическая лакуна поднята до нижней границы Разборова ранговой меры . Результатом является сильно экспоненциальная нижняя оценка монотонной сложности схемы явной функции, полученная с помощью характеризации Карчмера – Вигдерсона. ^[32] монотонного размера схемы с точки зрения сложности связи.

Открытые проблемы

Учитывая входную матрицу 0 или 1 $M_{f}=[f(x,y)]_{x,y\in \{0,1\}^{n}}$ , минимальное количество битов, которыми обмениваются для вычисления $f$ детерминированно в худшем случае, $D(f)$ , как известно, ограничена снизу логарифмом ранга матрицы $M_{f}$ . Гипотеза о лог-ранге предполагает, что сложность коммуникации, $D(f)$ , ограничено сверху постоянной степенью логарифма ранга $M_{f}$ . Поскольку D(f) ограничена сверху и снизу многочленами лог-ранга $(M_{f})$ , мы можем сказать, что D(f) полиномиально связана с лог-рангом $(M_{f})$ . Поскольку ранг матрицы является полиномиальным временем, вычислимым по размеру матрицы, такая верхняя граница позволит аппроксимировать сложность связи матрицы за полиномиальное время. Однако обратите внимание, что размер самой матрицы экспоненциально зависит от размера входных данных.

Предполагалось, что для рандомизированного протокола количество битов, которыми обмениваются в худшем случае, R(f), полиномиально связано со следующей формулой:

\log \min({\textrm {rank}}(M'_{f}):M'_{f}\in \mathbb {R} ^{2^{n}\times 2^{n}},(M_{f}-M'_{f})_{\infty }\leq 1/3).

Такие гипотезы о лог-ранге ценны, потому что они сводят вопрос о сложности связи матрицы к вопросу о линейно независимых строках (столбцах) матрицы. Эта конкретная версия, названная гипотезой логарифмического приближенного ранга, была недавно опровергнута Чаттопадьяем, Манде и Шерифом (2019). ^[33] используя удивительно простой контрпример. Это показывает, что суть проблемы сложности коммуникации, например, в приведенном выше случае EQ, заключается в выяснении того, где в матрице находятся входные данные, чтобы выяснить, эквивалентны ли они.

Приложения

Нижние границы сложности связи можно использовать для доказательства нижних границ сложности дерева решений , схем СБИС , структур данных, потоковых алгоритмов , компромиссов между пространством и временем для машин Тьюринга и многого другого. ^[2]

Конитцер и Сандхольм ^[34] изучил сложность коммуникации некоторых общих правил голосования , которые необходимы в политических и неполитических организациях. Сложность компиляции — это тесно связанное понятие, которое можно рассматривать как сложность связи за один раунд.

См. также

Проблема Гэпа-Хэмминга

Примечания

^ Jump up to: Перейти обратно: ^а ^б Яо, AC (1979), «Некоторые сложные вопросы, связанные с распределенными вычислениями», Proc. 11-го СТОЦ , 14 : 209–213.
^ Jump up to: Перейти обратно: ^а ^б Кушилевиц, Эяль; Нисан, Ноам (1997). Коммуникационная сложность . Издательство Кембриджского университета. ISBN 978-0-521-56067-2 .
^ Клив, Ричард; Ван Дам, Вим; Нильсен, Майкл; Тапп, Ален (1999). «Квантовая запутанность и коммуникационная сложность функции внутреннего продукта» . Квантовые вычисления и квантовые коммуникации . Конспекты лекций по информатике. Том. 1509. стр. 61–74. дои : 10.1007/3-540-49208-9_4 . ISBN 978-3-540-65514-5 .
^ Наваскес, Майкл; Гурьянова Елена; Хобан, Мэтти Дж.; Асин, Антонио (2015). «Почти квантовые корреляции» . Природные коммуникации . 6 . arXiv : 1403.4621 . дои : 10.1038/ncomms7288 . ПМИД 25697645 .
^ В. ван Дам, Нелокальность и коммуникационная сложность,доктор философии диссертация, Оксфордский университет (1999).
^ Г. Брассард, Х. Бурман, Н. Линден, А. А. Метот,А. Тапп, Ф. Унгер, Phys. Преподобный Летт. 96, 250401(2006).
^ Н. Бруннер и П. Скшипчик, Phys. Преподобный Летт. 102,160403 (2009).
^ П. Боттерон, А. Бродбент и М.-О. Пру, arXiv:2302.00488 .
^ Яо, Эндрю Чи-Чи (1977). «Вероятностные вычисления: к единой мере сложности» . 18-й ежегодный симпозиум по основам информатики (sfcs, 1977) . IEEE. дои : 10.1109/SFCS.1977.24 . ISSN 0272-5428 .
^ Разборов, Александр (1992). «О распределительной сложности дизъюнктности» . Теоретическая информатика . 106 (2): 385–390. дои : 10.1016/0304-3975(92)90260-М .
^ Бар-Йосеф, Зив; Джайрам, Т.С.; Кумар, Рави; Сивакумар, Д. (2004). «Подход информационной статистики к потокам данных и сложности связи» (PDF) . Журнал компьютерных и системных наук . 68 (4): 702–732. дои : 10.1016/j.jcss.2003.11.006 . Проверено 1 декабря 2023 г.
^ Барак, Боаз ; Браверман, Марк ; Чен, Си; Рао, Ануп (2013). «Как сжать интерактивное общение» (PDF) . SIAM Journal по вычислительной технике . 42 (3): 1327–1363. дои : 10.1137/100811969 .
^ Браверман, Марк ; Рао, Ануп (2014). «Информация равна амортизированному общению». Транзакции IEEE по теории информации . 60 (10): 6058–6069. arXiv : 1106.3595 . дои : 10.1109/TIT.2014.2347282 .
^ Браверман, Марк ; Гарг, Анкит; Панкратов, Денис; Вайнштейн, Омри (июнь 2013 г.). STOC '13: Материалы сорок пятого ежегодного симпозиума ACM по теории вычислений . Пало-Альто, Калифорния: ACM. стр. 151–160. дои : 10.1145/2488608.2488628 . ISBN 978-1-4503-2029-0 .
^ Браверман, Марк ; Мойтра, Анкур (1 июня 2013 г.). «Подход информационной сложности к расширенным формулировкам» . STOC '13: Материалы сорок пятого ежегодного симпозиума ACM по теории вычислений . Пало-Альто, Калифорния: ACM. стр. 161–170. дои : 10.1145/2488608.2488629 .
^ Вайнштейн, Омри (июнь 2015 г.). «Сложность информации и поиск интерактивного сжатия» . Новости ACM SIGACT . 46 (2): 41–64. дои : 10.1145/2789149.2789161 . Проверено 1 декабря 2023 г.
^ Яннакакис, М. (1991). «Выражение задач комбинаторной оптимизации с помощью линейных программ». Дж. Компьютер. Сист. Наука . 43 (3): 441–466. дои : 10.1016/0022-0000(91)90024-у .
^ Ловетт, Шачар, CSE 291: Сложность связи, зима 2019 г. Протоколы с неограниченными ошибками (PDF) , получено 9 июня 2019 г.
^ Гёос, Мика; Питасси, Тонианн; Уотсон, Томас (01 июня 2018 г.). «Пейзаж классов сложности связи» . Вычислительная сложность . 27 (2): 245–304. дои : 10.1007/s00037-018-0166-6 . ISSN 1420-8954 . S2CID 4333231 .
^ Шерстов, Александр А. (октябрь 2008 г.). «Сложность связи симметричных функций с неограниченной ошибкой». 2008 г. 49-й ежегодный симпозиум IEEE по основам информатики . стр. 384–393. дои : 10.1109/focs.2008.20 . ISBN 978-0-7695-3436-7 . S2CID 9072527 .
^ Форстер, Юрген (2002). «Линейная нижняя граница неограниченной вероятностной сложности связи» . Журнал компьютерных и системных наук . 65 (4): 612–625. дои : 10.1016/S0022-0000(02)00019-3 .
^ Алон, Н.; Франкл, П.; Родл, В. (октябрь 1985 г.). «Геометрическая реализация систем множеств и вероятностная сложность связи». 26-й ежегодный симпозиум по основам информатики (SFCS, 1985) . Портленд, Орегон, США: IEEE. стр. 277–280. CiteSeerX 10.1.1.300.9711 . дои : 10.1109/SFCS.1985.30 . ISBN 9780818606441 . S2CID 8416636 .
^ Раз, Ран ; Маккензи, Пьер (1999). «Выделение монотонной иерархии NC». Комбинаторика . 19 (3): 403–435. дои : 10.1007/s004930050062 .
^ Гёос, Мика; Питасси, Тонианн ; Уотсон, Томас (2018). «Детерминированная связь в зависимости от номера раздела» . SIAM Journal по вычислительной технике . 74 (6): 2435–2450. дои : 10.1137/16M1059369 .
^ Чаттопадхьяй, Аркадьев; Куцкий, Михал; Лофф, Бруно; Мухопадхьяй, Сагник (2019). «Теоремы моделирования через псевдослучайные свойства» . Вычислительная сложность . 28 (4): 617–659. arXiv : 1704.06807 . дои : 10.1007/s00037-019-00190-7 .
^ Ловетт, Шачар; Мека, Рагху; Мерц, Ян; Питасси, Тонианн ; Чжан, Цзяпэн (200). «Подъем с подсолнухами» (PDF) . 13-я конференция «Инновации в теоретической информатике» (ITCS 2022) . Том. 215. Международные труды Лейбница по информатике (LIPIcs). стр. 104:1–104:24. дои : 10.4230/LIPIcs.ITCS.2022.104 .
^ Гёос, Мика; Питасси, Тонианн ; Уотсон, Томас (2017). «Подъем запроса к коммуникации для BPP». 58-й ежегодный симпозиум IEEE по основам информатики (FOCS) , 2017 г. Беркли, Калифорния: IEEE. arXiv : 1703.07666 . дои : 10.1109/FOCS.2017.21 .
^ Гарг, Анкит; Гёос, Мика; Камат, Притиш; Соколов, Дмитрий (2020). «Нижние границы монотонной схемы по разрешению» . Теория вычислений . 16 :13:1–13:30. дои : 10.4086/toc.2020.v016a013 .
^ де Резенде, Сюзанна; Меир, Ор; Нордстрем, Якоб; Питасси, Тонианн ; Робер, Робер; Виньялс, Марк (2020). «Подъем с помощью простых гаджетов и приложений для решения сложных схем и доказательств». 61-й ежегодный симпозиум IEEE по основам информатики (FOCS) 2020 г. Виртуальная конференция: IEEE. стр. 24–30. arXiv : 2001.02144 . дои : 10.1109/FOCS46700.2020.00011 .
^ Шерстов, Александр (2011). «Метод шаблонной матрицы». SIAM Journal по вычислительной технике . 40 (6): 1969–2000. arXiv : 0906.4291 . дои : 10.1137/080733644 .
^ Питасси, Тонианн ; Робере, Роберт (2017). «Сильно экспоненциальные нижние границы для монотонных вычислений» (PDF) . STOC 2017: Материалы 49-го ежегодного симпозиума ACM SIGACT по теории вычислений . Монреаль: ACM. стр. 1246–1255. дои : 10.1145/3055399.3055478 .
^ Карчмер, Маурисио; Вигдерсон, Ави (1990). «Монотонные схемы для подключения требуют суперлогарифмической глубины» (PDF) . SIAM Journal по дискретной математике . 3 (2): 255–265. дои : 10.1137/0403021 .
^ Чаттопадхьяй, Аркадьев; Манде, Нихил С.; Шериф, Сухайль (2019). «Гипотеза о логарифмическом приближенном ранге неверна». 2019, Материалы 51-го ежегодного симпозиума ACM по теории вычислений: 42-53. https://doi.org/10.1145/3313276.3316353
^ Конитцер, Винсент; Сандхольм, Туомас (5 июня 2005 г.). «Коммуникационная сложность единых правил голосования» . Материалы 6-й конференции ACM по электронной коммерции . ЕС '05. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 78–87. дои : 10.1145/1064009.1064018 . ISBN 978-1-59593-049-1 .

Ссылки

Рао, Ануп; Иегудаофф, Амир (2020). Сложность связи и приложения . Кембридж: Издательство Кембриджского университета. ISBN 9781108671644 .
Кушилевиц, Эяль; Нисан, Ноам (2006). Коммуникационная сложность . Кембридж: Издательство Кембриджского университета. ISBN 978-0-521-02983-4 . OCLC 70764786 .
Брассар, Г. Сложность квантовой связи: обзор. https://arxiv.org/abs/quant-ph/0101005
Дитцфельбингер М., Дж. Хромкович Дж. и Г. Шнитгер, « Сравнение двух методов нижней границы сложности связи », Теорет. Вычислить. наук. 168, 1996. 39–51.
Раз, Ран . «Схема и сложность связи». В теории сложности вычислений. Стивен Рудич и Ави Вигдерсон, ред. Институт перспективных исследований Американского математического общества, 2004. 129–137.
AC Yao, «Некоторые сложные вопросы, связанные с распределенными вычислениями», Proc. 11-го STOC, стр. 209–213, 1979. 14
И. Ньюман, Частные и общие случайные биты в сложности связи , Information Processing Letters 39, 1991, стр. 67–71.

[yao1979-1] Jump up to: Перейти обратно: ^а ^б Яо, AC (1979), «Некоторые сложные вопросы, связанные с распределенными вычислениями», Proc. 11-го СТОЦ , 14 : 209–213.

[:0-2] Jump up to: Перейти обратно: ^а ^б Кушилевиц, Эяль; Нисан, Ноам (1997). Коммуникационная сложность . Издательство Кембриджского университета. ISBN 978-0-521-56067-2 .

[3] Клив, Ричард; Ван Дам, Вим; Нильсен, Майкл; Тапп, Ален (1999). «Квантовая запутанность и коммуникационная сложность функции внутреннего продукта» . Квантовые вычисления и квантовые коммуникации . Конспекты лекций по информатике. Том. 1509. стр. 61–74. дои : 10.1007/3-540-49208-9_4 . ISBN 978-3-540-65514-5 .

[4] Наваскес, Майкл; Гурьянова Елена; Хобан, Мэтти Дж.; Асин, Антонио (2015). «Почти квантовые корреляции» . Природные коммуникации . 6 . arXiv : 1403.4621 . дои : 10.1038/ncomms7288 . ПМИД 25697645 .

[5] В. ван Дам, Нелокальность и коммуникационная сложность,доктор философии диссертация, Оксфордский университет (1999).

[6] Г. Брассард, Х. Бурман, Н. Линден, А. А. Метот,А. Тапп, Ф. Унгер, Phys. Преподобный Летт. 96, 250401(2006).

[7] Н. Бруннер и П. Скшипчик, Phys. Преподобный Летт. 102,160403 (2009).

[8] П. Боттерон, А. Бродбент и М.-О. Пру, arXiv:2302.00488 .

[9] Яо, Эндрю Чи-Чи (1977). «Вероятностные вычисления: к единой мере сложности» . 18-й ежегодный симпозиум по основам информатики (sfcs, 1977) . IEEE. дои : 10.1109/SFCS.1977.24 . ISSN 0272-5428 .

[10] Разборов, Александр (1992). «О распределительной сложности дизъюнктности» . Теоретическая информатика . 106 (2): 385–390. дои : 10.1016/0304-3975(92)90260-М .

[11] Бар-Йосеф, Зив; Джайрам, Т.С.; Кумар, Рави; Сивакумар, Д. (2004). «Подход информационной статистики к потокам данных и сложности связи» (PDF) . Журнал компьютерных и системных наук . 68 (4): 702–732. дои : 10.1016/j.jcss.2003.11.006 . Проверено 1 декабря 2023 г.

[12] Барак, Боаз ; Браверман, Марк ; Чен, Си; Рао, Ануп (2013). «Как сжать интерактивное общение» (PDF) . SIAM Journal по вычислительной технике . 42 (3): 1327–1363. дои : 10.1137/100811969 .

[13] Браверман, Марк ; Рао, Ануп (2014). «Информация равна амортизированному общению». Транзакции IEEE по теории информации . 60 (10): 6058–6069. arXiv : 1106.3595 . дои : 10.1109/TIT.2014.2347282 .

[14] Браверман, Марк ; Гарг, Анкит; Панкратов, Денис; Вайнштейн, Омри (июнь 2013 г.). STOC '13: Материалы сорок пятого ежегодного симпозиума ACM по теории вычислений . Пало-Альто, Калифорния: ACM. стр. 151–160. дои : 10.1145/2488608.2488628 . ISBN 978-1-4503-2029-0 .

[15] Браверман, Марк ; Мойтра, Анкур (1 июня 2013 г.). «Подход информационной сложности к расширенным формулировкам» . STOC '13: Материалы сорок пятого ежегодного симпозиума ACM по теории вычислений . Пало-Альто, Калифорния: ACM. стр. 161–170. дои : 10.1145/2488608.2488629 .

[16] Вайнштейн, Омри (июнь 2015 г.). «Сложность информации и поиск интерактивного сжатия» . Новости ACM SIGACT . 46 (2): 41–64. дои : 10.1145/2789149.2789161 . Проверено 1 декабря 2023 г.

[17] Яннакакис, М. (1991). «Выражение задач комбинаторной оптимизации с помощью линейных программ». Дж. Компьютер. Сист. Наука . 43 (3): 441–466. дои : 10.1016/0022-0000(91)90024-у .

[18] Ловетт, Шачар, CSE 291: Сложность связи, зима 2019 г. Протоколы с неограниченными ошибками (PDF) , получено 9 июня 2019 г.

[19] Гёос, Мика; Питасси, Тонианн; Уотсон, Томас (01 июня 2018 г.). «Пейзаж классов сложности связи» . Вычислительная сложность . 27 (2): 245–304. дои : 10.1007/s00037-018-0166-6 . ISSN 1420-8954 . S2CID 4333231 .

[20] Шерстов, Александр А. (октябрь 2008 г.). «Сложность связи симметричных функций с неограниченной ошибкой». 2008 г. 49-й ежегодный симпозиум IEEE по основам информатики . стр. 384–393. дои : 10.1109/focs.2008.20 . ISBN 978-0-7695-3436-7 . S2CID 9072527 .

[21] Форстер, Юрген (2002). «Линейная нижняя граница неограниченной вероятностной сложности связи» . Журнал компьютерных и системных наук . 65 (4): 612–625. дои : 10.1016/S0022-0000(02)00019-3 .

[22] Алон, Н.; Франкл, П.; Родл, В. (октябрь 1985 г.). «Геометрическая реализация систем множеств и вероятностная сложность связи». 26-й ежегодный симпозиум по основам информатики (SFCS, 1985) . Портленд, Орегон, США: IEEE. стр. 277–280. CiteSeerX 10.1.1.300.9711 . дои : 10.1109/SFCS.1985.30 . ISBN 9780818606441 . S2CID 8416636 .

[23] Раз, Ран ; Маккензи, Пьер (1999). «Выделение монотонной иерархии NC». Комбинаторика . 19 (3): 403–435. дои : 10.1007/s004930050062 .

[24] Гёос, Мика; Питасси, Тонианн ; Уотсон, Томас (2018). «Детерминированная связь в зависимости от номера раздела» . SIAM Journal по вычислительной технике . 74 (6): 2435–2450. дои : 10.1137/16M1059369 .

[25] Чаттопадхьяй, Аркадьев; Куцкий, Михал; Лофф, Бруно; Мухопадхьяй, Сагник (2019). «Теоремы моделирования через псевдослучайные свойства» . Вычислительная сложность . 28 (4): 617–659. arXiv : 1704.06807 . дои : 10.1007/s00037-019-00190-7 .

[26] Ловетт, Шачар; Мека, Рагху; Мерц, Ян; Питасси, Тонианн ; Чжан, Цзяпэн (200). «Подъем с подсолнухами» (PDF) . 13-я конференция «Инновации в теоретической информатике» (ITCS 2022) . Том. 215. Международные труды Лейбница по информатике (LIPIcs). стр. 104:1–104:24. дои : 10.4230/LIPIcs.ITCS.2022.104 .

[27] Гёос, Мика; Питасси, Тонианн ; Уотсон, Томас (2017). «Подъем запроса к коммуникации для BPP». 58-й ежегодный симпозиум IEEE по основам информатики (FOCS) , 2017 г. Беркли, Калифорния: IEEE. arXiv : 1703.07666 . дои : 10.1109/FOCS.2017.21 .

[28] Гарг, Анкит; Гёос, Мика; Камат, Притиш; Соколов, Дмитрий (2020). «Нижние границы монотонной схемы по разрешению» . Теория вычислений . 16 :13:1–13:30. дои : 10.4086/toc.2020.v016a013 .

[29] де Резенде, Сюзанна; Меир, Ор; Нордстрем, Якоб; Питасси, Тонианн ; Робер, Робер; Виньялс, Марк (2020). «Подъем с помощью простых гаджетов и приложений для решения сложных схем и доказательств». 61-й ежегодный симпозиум IEEE по основам информатики (FOCS) 2020 г. Виртуальная конференция: IEEE. стр. 24–30. arXiv : 2001.02144 . дои : 10.1109/FOCS46700.2020.00011 .

[30] Шерстов, Александр (2011). «Метод шаблонной матрицы». SIAM Journal по вычислительной технике . 40 (6): 1969–2000. arXiv : 0906.4291 . дои : 10.1137/080733644 .

[31] Питасси, Тонианн ; Робере, Роберт (2017). «Сильно экспоненциальные нижние границы для монотонных вычислений» (PDF) . STOC 2017: Материалы 49-го ежегодного симпозиума ACM SIGACT по теории вычислений . Монреаль: ACM. стр. 1246–1255. дои : 10.1145/3055399.3055478 .

[32] Карчмер, Маурисио; Вигдерсон, Ави (1990). «Монотонные схемы для подключения требуют суперлогарифмической глубины» (PDF) . SIAM Journal по дискретной математике . 3 (2): 255–265. дои : 10.1137/0403021 .

[33] Чаттопадхьяй, Аркадьев; Манде, Нихил С.; Шериф, Сухайль (2019). «Гипотеза о логарифмическом приближенном ранге неверна». 2019, Материалы 51-го ежегодного симпозиума ACM по теории вычислений: 42-53. https://doi.org/10.1145/3313276.3316353

[34] Конитцер, Винсент; Сандхольм, Туомас (5 июня 2005 г.). «Коммуникационная сложность единых правил голосования» . Материалы 6-й конференции ACM по электронной коммерции . ЕС '05. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 78–87. дои : 10.1145/1064009.1064018 . ISBN 978-1-59593-049-1 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]