Complejidad de comunicación aleatoria cero error versus complejidad de comunicación determinista

Se sabe que para el error la definición de peor caso de complejidad de comunicación aleatoria y la definición de caso promedio son equivalentes. Pero cuando el error es , la complejidad de comunicación aleatoria en el peor de los casos es la misma que la complejidad de comunicación determinista. $\Theta(1)$ $0$

¿Se sabe que alguna función tiene una complejidad de comunicación determinista súper constante pero una complejidad de comunicación aleatoria constante de error cero?

En términos más generales, ¿qué es una función testigo que separa la complejidad de comunicación determinista y la complejidad de comunicación aleatoria de error cero?

Cualquier ayuda es apreciada.

communication-complexity sagnik
fuente

¿Te refieres a lo contrario (pequeño aleatorizado, pero grande determinista)?

Noam

Sí, lo siento mucho por ese desastre. Quiero una complejidad de comunicación aleatoria constante con cero errores, pero una complejidad de comunicación determinista súper constante. Estaba buscando el problema de la desunión set. Como y el protocolo Hastad-Wigderson ya proporciona un protocolo unilateral para la desunión de set de costo el problema se reduce a la prueba de un límite superior de un lado de error limitado aleatorio de costo constante para no-k-conjunto-desunión. ¿Ya hay un resultado?

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

Respuestas:

De hecho, para la disyunción de conjuntos de tamaño de elementos, se sabe que la complejidad de comunicación aleatoria de errores es , mientras que la complejidad determinista es . $\log(n)$ $n$ $0$ $\Theta(\log n)$ $\Theta(\log^2 n)$

Recuerde que puede haber como máximo una brecha cuadrática ya que la complejidad aleatorizada de error está limitada desde abajo por las complejidades no deterministas y co-no deterministas. $0$

Ver: http://mirror.theoryofcomputing.org/articles/v003a011/v003a011.pdf

Noam
fuente

Muchas gracias. Eso responde perfectamente a lo que quiero saber.

sagnik

Lo siento, haré eso.

sagnik