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

Фон:

Рассмотрим обычную двухстороннюю модель сложности коммуникации, где Алисе и Бобу даны битные строки и и они должны вычислить некоторую булеву функцию , где . $n$ $x$ $y$ $f(x,y)$ $f:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$

Мы определяем следующие величины:

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

$Pn(f)$ (номер раздела ): логарифм (основание 2) наименьшего числа монохроматических прямоугольников в разбиении (или непересекающемся покрытии), составляющий . $f$ $\{0,1\}^n \times \{0,1\}^n$

Монохроматический прямоугольник в - это подмножество такое, что принимает одно и то же значение (т. Е. Является монохроматическим) для всех элементов . $\{0,1\}^n \times \{0,1\}^n$ $R \times C$ $f$ $R \times C$

Также обратите внимание, что номер раздела отличается от «номера раздела протокола», который был предметом этого вопроса .

См. Текст Kushilevitz и Nisan для получения дополнительной информации. В их обозначениях то, что я определил как это . $Pn(f)$ $\log_2 C^D(f)$

Примечание . Эти определения легко обобщаются на небулевы функции , где выходные данные представляют собой некоторое большее множество. $f$ $f$

Известные результаты:

Известно, что является нижней границей , т. Е. Для всех (булевых или небулевых) , . Действительно, большинство методов нижней границы (или, возможно, все?) Для самом деле являются нижней границей . (Кто-нибудь может подтвердить, что это верно для всех методов нижней границы?) $Pn(f)$ $D(f)$ $f$ $Pn(f) \leq D(f)$ $D(f)$ $Pn(f)$

Также известно, что эта граница не более квадратично рыхлой (для булевых или небулевых функций), т. Е. $D(f) \leq (Pn(f))^2$ . Подводя итог, мы знаем следующее:

$Pn(f) \leq D(f) \leq (Pn(f))^2$

Предполагается, что . (Это открытая проблема 2.10 в тексте за текстом Кушилевица и Нисана.) Однако, насколько мне известно, наиболее известное разделение между этими двумя для булевых функций составляет только мультипликативный коэффициент 2, как показано в « Гипотеза о линейной матрице в сложности коммуникации ложна »Эяля Кушилевица, Натана Линиала и Рафаила Островского. $Pn(f) = \Theta(D(f))$

Точнее, они показывают бесконечное семейство булевых функций , таких что . $f$ $D(f) \geq (2 - o(1)) Pn(f)$

Вопрос:

Каково наиболее известное разделение между и для небулевых функций? Это все еще разделение фактора-2, упомянутое выше? $Pn(f)$ $D(f)$

Добавлено в версии 2 : Поскольку я не получил ответа в течение недели, я также рад услышать частичные ответы, предположения, слухи, неподтвержденные доказательства и т. Д.

lower-bounds communication-complexity Робин Котари
источник

Ты уверен насчет ? Лемма 3.8 в книге Юкны доказывает только , а в KN только состояние .

D (f) \leq (P n (f))^{2}

$D(f) \le (Pn(f))^2$

D (f) \leq 2 (P n (f))^{2}

$D(f) \le 2(Pn(f))^2$

D (f) = O ((P n (f))^{2})

$D(f) = O((Pn(f))^2)$

Андрас Саламон,

@ AndrásSalamon: я не слишком осторожно формулировал верхнюю границу, так как я ищу функции ближе к нижней границе, но я думаю, что достижимо. См. Теорему 2.2 в «Нижних границах сложности коммуникации» Троя Ли и Ади Шрайбмана.

(P n (f) + 1)^{2}

$(Pn(f)+1)^2$

Робин Котари

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

P n (f) \leq \log L (f) \leq D (f)

$Pn(f) \le \log L(f) \le D(f)$

L (f)

$L(f)$

f

$f$

\log L (f)

$\log L(f)$

P n (f)

$Pn(f)$

D (f) \leq 3.4 \log L (f)

$D(f) \le 3.4\,\log L(f)$

D (f)

$D(f)$

Андрас Саламон

См. Также соответствующий ответ cstheory.stackexchange.com/a/3352/109

Андраш Саламон

Ответы:

Этот вопрос был только что решен! Как я уже говорил, было известно, что

$Pn(f) \leq D(f) \leq (Pn(f))^2$ ,

но это было серьезной открытой проблемой, чтобы показать, что либо либо существует функция, для которой . $Pn(f) = \Theta(D(f))$ $Pn(f) = o(D(f))$

Несколько дней назад эту проблему решили Мика Гёес, Тонианн Питасси, Томас Уотсон ( http://eccc.hpi-web.de/report/2015/050/ ). Они показывают, что существует функция которая удовлетворяет $f$

$Pn(f) = \tilde{O}((D(f))^{2/3})$ .

Они также показывают оптимальный результат для односторонней версии , которую я , где вам нужно только покрыть 1-вход прямоугольниками. также удовлетворяет $Pn(f)$ $Pn_1(f)$ $Pn_1(f)$

$Pn_1(f) \leq D(f) \leq (Pn_1(f))^2$ ,

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

$Pn_1(f) = \tilde{O}((D(f))^{1/2})$ .

Робин Котари
источник

Это приятно завершает вопрос!

Андрас Саламон

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

Мне не ясно, насколько и могут отличаться в небулевом случае. $Pn(f)$ $D(f)$

В остальном я делаю эти комментарии более точными.

KN (Kushilevitz и Nisan в их учебнике 1997 года) обрисовывают в общих чертах три основных метода для булевых функций: размер набора обмана, размер монохромного прямоугольника и ранг матрицы связи.

Сначала дурачимся сетами. Околпачивать множество является монохроматическим: есть некоторый такой , что для каждых . Некоторое окончательное исправление необходимо учитывать другой цвет. Этого дополнительного шага можно избежать. Пусть функция . Пара различных элементов является слабо околпачивать для , если следует , что либо или . Множество является $S$ $z \in \{0,1\}$ $f(x,y) = z$ $(x,y)\in S$ $f \colon X \times Y \to \{0,1\}$ $(x_1,y_1),(x_2,y_2) \in X \times Y$ $f$ $f(x_1,y_1) = f(x_2,y_2)$ $f(x_1,y_2) \ne f(x_1,y_1)$ $f(x_2,y_1) \ne f(x_1,y_1)$ $S \subseteq X \times Y$ слабое обманчивое множество для если каждая отдельная пара элементов слабо обманывает. KN неявно заявляет после доказательства 1.20, что размер журнала слабого набора дурака является нижней границей сложности связи. $f$ $S$

Самый большой слабый набор для дурака выбирает репрезентативный элемент из каждого монохроматического прямоугольника в самой маленькой непересекающейся обложке набора. Следовательно, размер наибольшего слабого набора дурака не больше, чем (показатель степени) номера раздела. К сожалению, границы, предоставляемые наборами дурака, часто слабы. Доказательство KN 1.20 показывает , что любая функция отображение каждого элемент слабой околпачивать множества в монохроматический прямоугольник , содержащие этот элемент инъективно. Однако может быть много монохроматических прямоугольников в наименьшем непересекающемся покрытии, которые не появляются на изображении , причем каждый элемент слабо обманывает некоторые, но не все элементы $s$ $S$ $R_s$ $R$ $S$ $R$ $S$ И поэтому не могут быть просто добавлены в . На самом деле Dietzfelbinger, Hromkovič и Schnitger показали (DOI: 10.1016 / S0304-3975 (96) 00062-X ) , что для всех достаточно больших , по меньшей мере всех булевых функций на переменных имеют еще иметь (слабый) наборы дурака журнала размера . Таким образом, лог размера самого большого (слабого) набора обмана может быть экспоненциально меньше, чем сложность связи. $S$ $n$ $1/4$ $n$ $Pn(f) = n$ $O(\log n)$

Для ранга установление тесного соответствия между рангом матрицы функции и номером ее разбиения установило бы форму гипотезы о логарифмическом ранге (в зависимости от тесноты соответствия). Например, если существует постоянная такая, что для каждой булевой функции , то и гипотеза лог-ранга справедлива для семейств функций, для которых конечном итоге возрастает с, с показателем степени для любого достижимого для достаточно большого $a> 0$ $Pn(f) \le a\log rk(f)$ $f$ $D(f) \le (2a\log rk(f))^2$ $rk(f)$ $|X|+|Y|$ $2+\epsilon$ $\epsilon > 0$ $|X|+|Y|$ , (Напомним, что гипотеза Ловаша-Сакса лог-ранга говорит, что существует постоянная такая, что для любой булевой функции ; здесь есть ранг матрицы связи над реалами.) $c>0$ $D(f) \le (\log rk(f))^c$ $f$ $rk(f)$ $f$

Точно так же, если есть только один довольно большой монохроматический прямоугольник вместе со многими маленькими, тогда номер раздела дает более сильную границу, чем логарифм наибольшего монохроматического прямоугольника. Однако гипотеза лог-ранга также эквивалентна гипотезе о размере самого большого монохроматического прямоугольника (Nisan and Wigderson 1995, doi: 10.1007 / BF01192527 , теорема 2). Таким образом, использование монохроматических прямоугольников в настоящее время неизвестно, чтобы быть «таким же, как» с использованием номера раздела, но они тесно связаны, если гипотеза лог-ранга верна.

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

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

В отличие от приведенного выше обсуждения для булевых функций, для небулевых функций разрыв между и может быть экспоненциальным. В KN 2.23 приведен пример: пусть будет функцией, которая возвращает размер пересечений множеств, представленных двумя входными характеристическими векторами. Для этой функции лог-ранг равен . Теперь множество всех пар непересекающихся множеств имеет элементов. Насколько я могу судить, монохроматических прямоугольников не может быть больше, чем этот набор. Если это правильно, то , поэтому для этой функции , $D(f)$ $\log rk(f)$ $f$ $\log n$ $3^n$ $D(f) \ge Pn(f) \ge (2 - \log 3)n > 0.4n$ $D(f)$ $Pn(f)$ и размер логарифма самого большого монохроматического прямоугольника находится в пределах не более друг от друга, но экспоненциально далеко от ранга логарифма. Следовательно, небольшие различия между и могут быть возможны в небулевом случае, но они не связаны очевидным образом с лог-рангом матрицы функции . Мне не известны какие-либо опубликованные работы, в которых обсуждается, как эти меры связаны с небулевым случаем. $2.5$ $Pn(f)$ $D(f)$ $f$

Наконец, Dietzfelbinger et al. также определили расширенную границу набора дурака, обобщающую условие дурака от пар (подмножества «порядка 1») к большим подмножествам монохроматических элементов; расширенное условие обмана требует, чтобы подматрица, охватываемая монохроматическими элементами, не была монохроматической. Непонятно, как это ведет себя при увеличении порядка монохроматических подмножеств, так как необходимо разделить размер расширенного обмана, установленного по порядку, и рассмотреть наибольшее значение для всех порядков. Однако это понятие заканчивается тем, что является близкой нижней границей к . $Pn(f)$

Андраш Саламон
источник

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

P n (f)

$Pn(f)$

D (f)

$D(f)$

D (f)

$D(f)$

P n (f)

$Pn(f)$

Робин Котари

@Robin: извинения за отсутствие ясности; ключевые фразы «тесно связаны» и «сколько ... может отличаться». Я беру с учетом известных неравенств, таких как , где - количество записей в наибольшем монохроматическом прямоугольнике в матрице , а область равна . Мой комментарий о том, насколько близки эти неравенства, например, избегают ли они экспоненциальных пропусков, и почему размер множества слабых дурачек более полезен, чем обычное понятие (монохроматическая версия может быть экспоненциально меньше, чем предел ранга).

D (f) \geq P n (f) \geq 2 n - \log m o n o (f)

$D(f) \ge Pn(f) \ge 2n - \log mono(f)$

m o n o (f)

$mono(f)$

f

$f$

f

$f$

2^{n} \times 2^{n}

$2^n\times 2^n$

Андрас Саламон