Это продолжение моего предыдущего вопроса о нижних границах связи для частичных булевых функций .
Может ли кто-нибудь предложить какую-либо ссылку на нижние границы для недетерминированного многопартийного общения? Я просматривал статьи в этой области, но все, кажется, демонстрируют разделение следующего типа: нижняя граница для рандомизированного протокола и (меньшая) верхняя граница для недетерминированного протокола. См., Например, David, Pitassi и Viola 2009 , Gavinsky and Sherstov 2010 , Beame, David, Pitassi и Woelfel 2010 .
В частности, я хотел бы знать, существует ли норма (например, для k сторон), которая ограничивает недетерминированные многопартийные коммуникации в модели «число в лбу» или «число в руке».
Ответы:
После долгих чтений я нашел следующую статью
Трой Ли и Ади Шрайбман. В многопартийной модели «число на лбу» трудно отделиться . В материалах IEEE 23-й ежегодной конференции по вычислительной сложности . 22-26 июня 2008 г.
Авторы показывают, что рандомизированное сообщение с ограниченной ошибкой ограничено снизу приближенной нормой пересечения цилиндров (см. Определение 5 в статье).μα
Затем они делают следующее замечание.
Есть ли какая-либо другая норма, более сильная, чем расхождение, которая может быть использована для нижних границ в недетерминированной многопартийной коммуникации? Или это туго? Эти результаты очень недавние, так что, возможно, это открытая проблема. Продолжение этого вопроса здесь .
источник