Коммуникационная сложность - Communication complexity

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

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

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

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

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

${\ Displaystyle D (е) =}$ минимальное количество бит, которыми обмениваются Алиса и Боб в худшем случае.

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

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

${\ displaystyle T_ {h} = \ {(x, y): {\ text {the}} k {\ text {-биты обмениваются при вводе}} (x, y) {\ text {is}} h \} }$

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

Пример: ${\ displaystyle EQ}$

Мы рассматриваем случай, когда Алиса и Боб пытаются определить, равны ли их входные строки. Формально определить Равенства функцию, обозначенную , по если . Как мы продемонстрируем ниже, решение любого детерминированного протокола связи в худшем случае требует обмена данными. В качестве примера разминки рассмотрим простой случай . Функция равенства в этом случае может быть представлена ​​следующей матрицей. Строки представляют все возможности , столбцы - возможности . ${\ Displaystyle EQ: \ {0,1 \} ^ {n} \ times \ {0,1 \} ^ {n} \ rightarrow \ {0,1 \}}$${\ displaystyle EQ (x, y) = 1}$${\ displaystyle x = y}$${\ displaystyle EQ}$${\ displaystyle n}$${\ Displaystyle х, у \ в \ {0,1 \} ^ {3}}$${\ displaystyle x}$${\ displaystyle 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 только при равенстве (т. Е. По диагонали). Также довольно легко увидеть, как передача одного бита делит ваши возможности пополам. Если вы знаете, что первый бит равен 1, вам нужно учитывать только половину столбцов (где может быть 100, 101, 110 или 111). ${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle y}$${\ displaystyle y}$

Теорема: ${\ Displaystyle D (EQ) = п}$

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

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

Рандомизированная коммуникационная сложность

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

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

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

${\ displaystyle \ 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

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

Понятно, если , значит , так . Если x не равно y , возможно , что это даст Бобу неправильный ответ. Как это произошло? ${\ displaystyle x = y}$${\ Displaystyle Z \ CDOT Икс = Z \ CDOT Y}$${\ displaystyle Prob_ {z} [Принять] = 1}$${\ Displaystyle Z \ CDOT Икс = Z \ CDOT Y}$

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

${\ displaystyle {\ begin {case} 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 {case}}}$

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

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

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

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

Пример: GH

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

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

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

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

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

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

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

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

Давайте определим и будем вероятностями, что и вычислим правильное значение для входных данных . ${\ Displaystyle р (х, у)}$${\ Displaystyle р '_ {R} (х, у)}$${\ displaystyle P}$${\ displaystyle P '_ {R}}$${\ Displaystyle (х, у)}$

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

${\ Displaystyle \ Pr _ {R} [| p '_ {R} (x, y) -p (x, y) | \ geq 0,1] \ Leq 2 \ exp (-2 (0,1) ^ {2} \ cdot 100n) <2 ^ {- 2n}}$

Таким образом, когда мы не исправили: ${\ Displaystyle (х, у)}$

${\ Displaystyle \ Pr _ {R} [\ существует (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}$

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

${\ displaystyle | p '_ {R_ {0}} (x, y) -p (x, y) | <0,1}$

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

Сложность квантовой коммуникации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

Смотрите также

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

Примечания

использованная литература

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