Рандомизированная сложность связи с нулевой ошибкой и детерминированная сложность связи

Известно, что для ошибки определение рандомизированной сложности связи в худшем случае и определение среднего случая эквивалентны. Но когда ошибка равна , сложность рандомизированной связи в худшем случае такая же, как сложность детерминированной связи. $\Theta(1)$ $0$

Известно ли, что любая функция имеет сверхконстантную детерминированную сложность связи, но постоянную нулевую ошибку рандомизированной сложности связи?

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

Любая помощь приветствуется.

communication-complexity sagnik
источник

Вы имеете в виду обратное (небольшое рандомизированное, но большое детерминированное)?

Noam

Да, очень жаль за этот беспорядок. Мне нужна постоянная сложность коммуникации с нулевой ошибкой, но сверхконстантная сложность связи. Я искал проблему несвязности множества . Поскольку и протокол Хастада-Вигдерсона уже дают односторонний протокол для множественного дизъюнкта При стоимости проблема сводится к доказательству случайной верхней грани рандомизированной ограниченной ошибки для не-k-множества-дизъюнктности. Есть ли уже результат?

k

$k$

R_{0} (f) = O (m a x {R^{1} (f), R^{1} (not f)})

$R_0(f)=O(max\{R^1(f), R^1(\text{not }f)\})$

k

$k$

O (k)

$O(k)$

sagnik

Ответы:

Действительно, для непересекаемости множеств размера из элементов известно, что случайная сложность связи с ошибками равна , а детерминированная сложность - . $\log(n)$ $n$ $0$ $\Theta(\log n)$ $\Theta(\log^2 n)$

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

Смотрите: http://mirror.theoryofcomputing.org/articles/v003a011/v003a011.pdf

Ноам
источник

Большое спасибо. Это прекрасно отвечает тому, что я хочу знать.

Сагник

Извините, я сделаю это.

sagnik