Нижние оценки для недетерминированного многопартийного общения

11

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

Может ли кто-нибудь предложить какую-либо ссылку на нижние границы для недетерминированного многопартийного общения? Я просматривал статьи в этой области, но все, кажется, демонстрируют разделение следующего типа: нижняя граница для рандомизированного протокола и (меньшая) верхняя граница для недетерминированного протокола. См., Например, David, Pitassi и Viola 2009 , Gavinsky and Sherstov 2010 , Beame, David, Pitassi и Woelfel 2010 .

В частности, я хотел бы знать, существует ли норма (например, для k сторон), которая ограничивает недетерминированные многопартийные коммуникации в модели «число в лбу» или «число в руке».γkk

Маркос Вильягра
источник
я должен поместить часть редактирования как ответ и сделать другой вопрос?
Маркос Вильягра
Вы должны поставить новый результат, который вы нашли в ответе. (возможно, вы получите значок для самообучения!) Что касается новой задачи, то можно оставить ее в том же вопросе.
Сянь-Чи Чанг 之 之
Я думаю, что это хорошо, чтобы добавить его в качестве ответа. Вы задали вопрос некоторое время назад и ждали ответов. Затем вы нашли один - это именно то, для чего предназначен значок самообучения
Суреш Венкат

Ответы:

4

После долгих чтений я нашел следующую статью

Трой Ли и Ади Шрайбман. В многопартийной модели «число на лбу» трудно отделиться . В материалах IEEE 23-й ежегодной конференции по вычислительной сложности . 22-26 июня 2008 г.

Авторы показывают, что рандомизированное сообщение с ограниченной ошибкой ограничено снизу приближенной нормой пересечения цилиндров (см. Определение 5 в статье).μα

Теорема 6: Пусть М знак -тензорному, и 0 & le ; & epsi ; < 1 / 2 . Тогда R k ϵ ( M ) log ( μ α ( M ) ) - log ( α ϵ ), где α ϵ = 1 / ( 1 - 2 ϵ ) и α α ϵ .k0ϵ<1/2Rϵk(M)log(μα(M))log(αϵ)αϵ=1/(12ϵ)ααϵ

Затем они делают следующее замечание.

logμ

αMμ(M)=1/Disc(M)Disc(M)MkΩ(logn/(k1))Ω(n1/(k+1)22k)μα

Есть ли какая-либо другая норма, более сильная, чем расхождение, которая может быть использована для нижних границ в недетерминированной многопартийной коммуникации? Или это туго? Эти результаты очень недавние, так что, возможно, это открытая проблема. Продолжение этого вопроса здесь .

Маркос Вильягра
источник
Вы можете принять свой собственный ответ :). Кроме того, может быть, вы можете задать новый вопрос отдельно?
Суреш Венкат
сделанный. Новый вопрос теперь в cstheory.stackexchange.com/questions/3614/…
Маркос Вильягра
как раз перед тем, как принять его, я хотел бы подождать и посмотреть, знает ли кто-нибудь какую-либо другую нижнюю границу, например, теоретико-информационную границу
Маркос Вильягра