Complejidad de comunicación aleatoria unidireccional de desunión

Estoy buscando una referencia para la complejidad de la comunicación aleatoria unidireccional (clásica) cuando el universo puede ser grande. Digamos que Alice y Bob tienen conjuntos de tamaño elegidos de un universo de tamaño y Bob quiere determinar si la intersección de sus conjuntos está vacía o no. Me gustaría un problema de error , digamos. $m$ $U$ $<1/3$

Puedo encontrar el límite inferior estándar de y algunos funcionan en la complejidad de la comunicación bidireccional, pero ¿hay alguna referencia para algo más estricto para unidireccional? $\Omega(m)$

EDITAR: debería haber especificado que estoy interesado en el modelo de aleatoriedad privada (no en moneda pública).

cc.complexity-theory reference-request lower-bounds communication-complexity Rafael
fuente

¿Se eligen los conjuntos al azar, o solo la estrategia de comunicación?

mjqxxxx

La aleatorización solo se refiere al hecho de que Alice y Bob pueden usar bits aleatorios.

Raphael

¿Realmente está considerando la comunicación unidireccional (Alice envía un mensaje a Bob que luego envía la respuesta) o la comunicación "simultánea" (Alice y Bob envían un mensaje a un árbitro que anuncia la respuesta). En el primer caso, público y privado la aleatoriedad es la misma y parece que las respuestas a continuación (es decir, el blog de Mihai) resuelven la pregunta.

Noam

Es el primer caso de comunicación unidireccional, tal como la define, en la que estoy interesado. Espero algo apretado en toda la gama de tamaños de universo. Si entiendo correctamente, la publicación de Mihai nos da un límite superior de y tenemos un límite inferior de que todavía deja un hueco.

O (m \log m + \log U)

$O(m \log{m} + \log{U})$

min ((\binom{U}{m}), m \log m)

$\min(\binom{U}{m}, m\log{m})$

Raphael

Me refiero a por supuesto.

Ω (min (\log (\binom{U}{m}), m \log m))

$\Omega(\min(\log{\binom{U}{m}}, m\log{m}))$

Raphael

Respuestas:

La respuesta es . En el modelo de monedas públicas, tenemos (como se describió anteriormente) . Como Yuval sugirió anteriormente, para el límite superior en el modelo de monedas privadas solo necesitamos un aditivo bits (consulte el teorema 3.14 en el libro K&N ) , donde es la longitud de la codificación de la entrada ( ). Para el límite inferior adicional de en el modelo de moneda privada, es suficiente concentrarse en el caso (ya que los otros elementos se pueden arreglar para que sean todos diferentes), que es solo la función de igualdad en $\Theta(m\log m + \log\log |U|)$ $\Theta(m\log m)$ $O(\log n)=O(\log m + \log\log |U|)$ $n$ $n=m\log|U|$ $\Omega(\log\log |U|)$ $m=1$ $\log |U|$ -cadenas de bits, cuya complejidad de monedas privadas es logarítmica en eso (ejemplo 3.9 en K&N).

Noam
fuente

Gracias, eso es perfecto, sin embargo, ¿no necesitamos también compararlo con que sea menor que dependiendo de cómo relacione con . En el caso extremo, si , Alice no necesita decir mucho.

\log (\binom{U}{m})

$\log {\binom{U}{m}}$

m \log m

$m\log{m}$

U

$U$

m

$m$

U = m

$U=m$

Raphael

sí, esto es para grande (al menos ), de lo contrario, el límite inferior mencionado en la publicación de Mihai falla.

U

$U$

m^{1 + ϵ}

$m^{1+\epsilon}$

Noam

esto resuelve la pregunta :-)

Marcos Villagra

Por cierto, siempre quise preguntarte, ¿por qué es el límite inferior general de contenido en el libro K&N? Implicaría automáticamente cosas como el teorema 3.9.

\log \log | X | \leq R (f)

$\log \log |X| \le R(f)$

domotorp

¿Es conocido / obvio que es ajustado para universos de menor tamaño? Por ejemplo, diga .

\log (\binom{U}{m})

$\log{\binom{U}{m}}$

U = m \log m

$U = m \log{m}$

Raphael

Para cualquier número de rondas, el límite inferior de la desunión es (véase La complejidad de comunicación probabilística de la intersección de conjuntos. SIAM J. Matemática discreta. Volumen 5, Número 4, págs. 545-557 (noviembre de 1992) ) . $\Omega(n)$

Para 1 sentido, Kremer, Nisan y Ron mostraron que para cualquier , , donde es el 1- aleatorizado forma complejidad de comunicación de con error , y es la dimensión VC de . Entonces tenemos que . Pero, de hecho, hay un límite inferior ajustado para DISJ, que es (véase el blog de Mihai Patrascu ). $f$ $R_\epsilon^1(f)=\Omega(VC(f))$ $R_\epsilon^1(f)$ $f$ $\epsilon$ $VC(f)$ $f$ $VC(DISJ)=n$ $\Omega(n\log n)$

Marcos Villagra
fuente

El blog de Mihai Patrascu dice que se puede lograr incluso para universos grandes con el uso de una función hash universal. Esto tiene sentido si Alice y Bob tienen una fuente compartida de aleatoriedad; pero si tienen fuentes independientes, ¿Alice no tiene que decirle a Bob qué función hash está usando? ¿Cuánto espacio ocupa eso?

O (n \log n)

$O(n\log n)$

mjqxxxx

Hay un truco que muestra que la aleatoriedad pública es lo mismo que la aleatoriedad privada: use un límite de Chernoff para mostrar que existe un espacio de muestra de tamaño polinómico [en el logaritmo del número de entradas posibles] que se aproxima a la probabilidad de éxito "lo suficientemente bien" en todas las entradas; Alice elige uno de estos puntos y envía su índice de tamaño logarítmico a Bob. Este truco no se aplica directamente en este caso (ya que hay infinitas entradas), pero puede ser adaptado de alguna manera.

Yuval Filmus

¡Gracias! Debería haber especificado aleatoriedad privada en la pregunta. Arreglando ahora.

Raphael

La complejidad aleatoria de monedas privadas (de una y dos vías) de CUALQUIER función es al menos, por ejemplo, en su caso al menos , que sería si es pequeño, lo que puede dar un límite inferior mejor. Este resultado se menciona en el documento seminal de Yao sobre CC, puede encontrar la prueba en mi tesis de maestría, lema 3.8 y alrededor: http://www.cs.elte.hu/~dom/cikkek/szakdolgozat.pdf $\log \log |\text{size}|$ $\log \log {U \choose m}$ $\log \log U$ $m$

Por supuesto, esto es sólo un límite inferior, tal vez su es una coincidencia límite superior como . $m + \log \log U$

domotorp
fuente