Complejidad de comunicación determinista versus número de partición

Antecedentes:

Considere el modelo habitual de dos partes de la complejidad de la comunicación donde Alice y Bob reciben cadenas de $n$ bits $x$ e $y$ y tienen que calcular alguna función booleana $f(x,y)$ , donde $f:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ .

Definimos las siguientes cantidades:

$D(f)$ (la complejidad de comunicación determinista de $f$ ): el número mínimo de bits que Alice y Bob necesitan para comunicarse para calcular $f(x,y)$ determinista.

$Pn(f)$ (el número de partición de $f$ ): el logaritmo (base 2) del número más pequeño de rectángulos monocromáticos en una partición (o una cubierta disjunta) de $\{0,1\}^n \times \{0,1\}^n$ .

Un rectángulo monocromático en es un subconjunto tal que toma el mismo valor (es decir, es monocromático) en todos los elementos de $\{0,1\}^n \times \{0,1\}^n$ $R \times C$ $f$ . $R \times C$

También tenga en cuenta que el número de partición es diferente del "número de partición de protocolo", que fue el tema de esta pregunta .

Vea el texto de Kushilevitz y Nisan para más información. En su notación, lo que he definido como es $Pn(f)$ . $\log_2 C^D(f)$

Nota : Estas definiciones se generalizan fácilmente a funciones no booleanas , donde la salida de es un conjunto más grande. $f$ $f$

Resultados conocidos:

Se sabe que es un límite inferior en , es decir, para todos (booleanos o no booleanos) , . De hecho, la mayoría de las técnicas de límite inferior (¿o quizás todas?) Para realidad es un límite inferior $Pn(f)$ $D(f)$ $f$ $Pn(f) \leq D(f)$ $D(f)$ . (¿Alguien puede confirmar que esto es cierto para todas las técnicas de límite inferior?) $Pn(f)$

También se sabe que este límite es a lo sumo cuadráticamente suelto (para funciones booleanas o no booleanas), es decir, . Para resumir, sabemos lo siguiente: $D(f) \leq (Pn(f))^2$

$Pn(f) \leq D(f) \leq (Pn(f))^2$

Se conjetura que $Pn(f) = \Theta(D(f))$ . (Este es el problema abierto 2.10 en el texto por texto de Kushilevitz y Nisan.) Sin embargo, que yo sepa, la separación más conocida entre estos dos para las funciones booleanas es solo por un factor multiplicativo de 2, como se muestra en "El La conjetura de matriz lineal en la complejidad de la comunicación es falsa "por Eyal Kushilevitz, Nathan Linial y Rafail Ostrovsky.

Más precisamente, exhiben una familia infinita de funciones booleanas , tal que . $f$ $D(f) \geq (2 - o(1)) Pn(f)$

Pregunta:

¿Cuál es la separación más conocida entre y para funciones no booleanas? ¿Sigue siendo la separación del factor 2 mencionada anteriormente? $Pn(f)$ $D(f)$

Agregado en v2 : como no he recibido una respuesta en una semana, también estoy feliz de escuchar respuestas parciales, conjeturas, rumores, evidencia anecdótica, etc.

lower-bounds communication-complexity Robin Kothari
fuente

¿Está seguro acerca de

? El lema 3.8 en el libro de Jukna solo prueba

, y KN solo indica

D (f) \leq (P n (f))^{2}

$D(f) \le (Pn(f))^2$

D (f) \leq 2 (P n (f))^{2}

$D(f) \le 2(Pn(f))^2$

D (f) = O ((P n (f))^{2})

$D(f) = O((Pn(f))^2)$

András Salamon

@ AndrásSalamon: No tuve demasiado cuidado al establecer el límite superior ya que estoy buscando funciones más cercanas al límite inferior, pero creo que

es alcanzable. Vea el Teorema 2.2 en "Límites más bajos en la complejidad de la comunicación" de Troy Lee y Adi Shraibman.

(P n (f) + 1)^{2}

$(Pn(f)+1)^2$

Robin Kothari

Dado que

, donde

es el número más pequeño de hojas en un árbol de protocolo de comunicación para

, es posible obtener un límite inferior para

que técnicamente no es un límite inferior para

. Sin embargo, dado que

P n (f) \leq \log L (f) \leq D (f)

$Pn(f) \le \log L(f) \le D(f)$

L (f)

$L(f)$

f

$f$

\log L (f)

$\log L(f)$

P n (f)

$Pn(f)$

, tal límite inferior establecería esencialmente una aproximación cercana al valor preciso de

D (f) \leq 3.4 \log L (f)

$D(f) \le 3.4\,\log L(f)$

D (f)

$D(f)$

András Salamon

Consulte también la respuesta relacionada cstheory.stackexchange.com/a/3352/109

András Salamon

Respuestas:

¡Esta pregunta acaba de ser resuelta! Como mencioné, se sabía que

, $Pn(f) \leq D(f) \leq (Pn(f))^2$

pero fue un gran problema abierto mostrar que o que existe una función para la cual $Pn(f) = \Theta(D(f))$ $Pn(f) = o(D(f))$ .

Hace unos días, esto fue resuelto por Mika Göös, Toniann Pitassi, Thomas Watson ( http://eccc.hpi-web.de/report/2015/050/ ). Muestran que existe una función que satisface $f$

. $Pn(f) = \tilde{O}((D(f))^{2/3})$

También muestran un resultado óptimo para la versión unilateral de , que denotaré por , donde solo necesita cubrir las entradas 1 con rectángulos. también satisface $Pn(f)$ $Pn_1(f)$ $Pn_1(f)$

, $Pn_1(f) \leq D(f) \leq (Pn_1(f))^2$

y muestran que esta es la mejor relación posible entre las dos medidas, ya que exhiben una función que satisface $f$

. $Pn_1(f) = \tilde{O}((D(f))^{1/2})$

Robin Kothari
fuente

¡Esto termina bien la pregunta!

András Salamon

Usted observa que los límites inferiores en están estrechamente relacionados con todas las técnicas existentes de límite inferior. Para las funciones booleanas esto parece ser cierto, siempre y cuando la conjetura log-rank sea verdadera. Sin embargo, puede ser exponencialmente más grande que el límite del conjunto engañoso. $Pn(f)$ $Pn(f)$

No está claro para mí cuánto y pueden diferir en el caso no booleano. $Pn(f)$ $D(f)$

En el resto, hago estos comentarios más precisos.

KN (Kushilevitz y Nisan en su libro de texto de 1997) describen las tres técnicas básicas para las funciones booleanas: tamaño de un conjunto engañoso, tamaño de un rectángulo monocromático y rango de la matriz de comunicación.

Primero, juegos engañosos. Un conjunto engañar es monocromática: hay una cierta tal que para cada . Se necesita un parche final para tener en cuenta el otro color. Este paso adicional se puede evitar. Sea una función. Un par de elementos distintos $S$ $z \in \{0,1\}$ $f(x,y) = z$ $(x,y)\in S$ $f \colon X \times Y \to \{0,1\}$ estáengañando débilmentepara si implica que o $(x_1,y_1),(x_2,y_2) \in X \times Y$ $f$ $f(x_1,y_1) = f(x_2,y_2)$ $f(x_1,y_2) \ne f(x_1,y_1)$ . Un conjunto es unconjunto de engaño débilpara si cada par distinto de elementos de es débilmente engañoso. KN indica implícitamente después de la prueba de 1.20 que el tamaño de registro de un conjunto de engaño débil es un límite inferior para la complejidad de la comunicación. $f(x_2,y_1) \ne f(x_1,y_1)$ $S \subseteq X \times Y$ $f$ $S$

$s$ $S$ $R_s$ $R$ $S$ $R$ $S$ $S$ $n$ $1/4$ $n$ $Pn(f) = n$ $O(\log n)$

$a> 0$ $Pn(f) \le a\log rk(f)$ $f$ $D(f) \le (2a\log rk(f))^2$ $rk(f)$ $|X|+|Y|$ $2+\epsilon$ $\epsilon > 0$ $|X|+|Y|$ $c>0$ $D(f) \le (\log rk(f))^c$ $f$ $rk(f)$ $f$

Del mismo modo, si solo hay un rectángulo monocromático bastante grande junto con muchos pequeños, entonces el número de partición da un límite más fuerte que el tamaño de registro de un rectángulo monocromático más grande. Sin embargo, la conjetura de rango logarítmico también es equivalente a una conjetura sobre el tamaño de un rectángulo monocromático más grande (Nisan y Wigderson 1995, doi: 10.1007 / BF01192527 , Teorema 2). Por lo tanto, el uso de rectángulos monocromáticos no se conoce actualmente como "igual que" usar el número de partición, pero están estrechamente relacionados si se cumple la conjetura del rango logarítmico.

En resumen, el tamaño de registro de un conjunto de engaño débil más grande puede ser exponencialmente menor que el número de partición. Puede haber espacios entre las otras técnicas de límite inferior y el número de partición, pero si la conjetura de rango logarítmico se mantiene, estos espacios son pequeños.

Mediante el uso de nociones de tamaño que extienden el habitual (de cardinalidad), el tamaño de cualquier rectángulo monocromático se puede utilizar para generalizar conjuntos engañosos y para reducir la complejidad de la comunicación (ver KN 1.24). No estoy seguro de cuán cerca debe estar el "tamaño" más grande generalizado de cualquier rectángulo monocromático a la complejidad de la comunicación.

$D(f)$ $\log rk(f)$ $f$ $\log n$ $3^n$ $D(f) \ge Pn(f) \ge (2 - \log 3)n > 0.4n$ $D(f)$ $Pn(f)$ $2.5$ $Pn(f)$ $D(f)$ $f$

$Pn(f)$

András Salamon
fuente

P n (f)

$Pn(f)$

D (f)

$D(f)$

D (f)

$D(f)$

P n (f)

$Pn(f)$

D (f) \geq P n (f) \geq 2 n - \log m o n o (f)

$D(f) \ge Pn(f) \ge 2n - \log mono(f)$

m o n o (f)

$mono(f)$

f

$f$

f

$f$

2^{n} \times 2^{n}

$2^n\times 2^n$ . Mi comentario es sobre cuán cercanas son Estas desigualdades son, por ejemplo, si evitan brechas exponenciales y por qué el tamaño del conjunto de engaño débil es más útil que la noción habitual (la versión monocromática puede ser exponencialmente más pequeña que el límite de rango).

András Salamon