Hispanopedia Wiki
Articulo de referencia

Complejidad de la comunicación

En la ciencia de la computación teórica , la complejidad de la comunicación estudia la cantidad de comunicación necesaria para resolver un problema cuando la entrada al problema...

Hispanopedia WikiContenido en espanolLectura gratuita

En la ciencia de la computación teórica , la complejidad de la comunicación estudia la cantidad de comunicación necesaria para resolver un problema cuando la entrada al problema se distribuye entre dos o más partes. El estudio de la complejidad de la comunicación fue introducido por primera vez por Andrew Yao en 1979, mientras estudiaba el problema de la computación distribuida entre varias máquinas. [ 1 ] El problema generalmente se plantea de la siguiente manera: dos partes (tradicionalmente llamadas Alice y Bob ) reciben cada una una (potencialmente diferente)norte{\displaystyle n}- cadena de bitsincógnita{\displaystyle x}yy{\displaystyle y}. El objetivo es que Alice calcule el valor de una determinada función,F(incógnita,y){\displaystyle f(x,y)}, eso depende de ambosincógnita{\displaystyle x}yy{\displaystyle y}, con la menor cantidad de comunicación entre ellos.

Si bien Alice y Bob siempre pueden tener éxito haciendo que Bob envíe todo sunorte{\displaystyle n}-cadena de bits a Alice (quien luego calcula la funciónF{\displaystyle f}), la idea aquí es encontrar formas ingeniosas de calcularF{\displaystyle f}con menos denorte{\displaystyle n}bits de comunicación. Cabe señalar que, a diferencia de la teoría de la complejidad computacional , la complejidad de la comunicación no se ocupa de la cantidad de cálculos realizados por Alice o Bob, ni del tamaño de la memoria utilizada, ya que generalmente no asumimos nada sobre la capacidad computacional de Alice o Bob.

Este problema abstracto con dos partes (denominado complejidad de comunicación entre dos partes), y su forma general con más de dos partes , es relevante en muchos contextos. En el diseño de circuitos VLSI , por ejemplo, se busca minimizar el consumo de energía reduciendo la cantidad de señales eléctricas transmitidas entre los diferentes componentes durante un cálculo distribuido. El problema también es relevante en el estudio de estructuras de datos y en la optimización de redes informáticas. Para obtener información general sobre el tema, consulte los libros de texto de Rao y Yehudayoff (2020) y Kushilevitz y Nisan (2006) .

Definición formal

DejarF:incógnita×Y→Z{\displaystyle f:X\times Y\rightarrow Z}donde asumimos en el caso típico queincógnita=Y={0,1}norte{\displaystyle X=Y=\{0,1\}^{n}}yZ={0,1}{\displaystyle Z=\{0,1\}}Alice sostiene unnorte{\displaystyle n}cadena de bits incógnita∈incógnita{\displaystyle x\in X}mientras Bob sostiene unnorte{\displaystyle n}cadena de bits y∈Y{\displaystyle y\in Y}Al comunicarse entre sí bit a bit (adoptando algún protocolo de comunicación acordado de antemano), Alice y Bob desean calcular el valor deF(incógnita,y){\displaystyle f(x,y)}de tal manera que al menos una de las partes conozca el valor al final de la comunicación. En este punto, la respuesta puede comunicarse de vuelta, de modo que, a costa de un bit adicional, ambas partes conocerán la respuesta. La complejidad de comunicación en el peor de los casos de este problema de comunicación de computaciónF{\displaystyle f}, denotado comoD(F){\displaystyle D(f)}, entonces se define como

D(F)={\displaystyle D(f)=}Número mínimo de bits intercambiados entre Alice y Bob en el peor de los casos.

Como se observó anteriormente, para cualquier funciónF:{0,1}norte×{0,1}norte→{0,1}{\displaystyle f:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}, tenemosD(F)≤norte{\displaystyle D(f)\leq n}. Utilizando la definición anterior, es útil pensar en la funciónF{\displaystyle f}como una matrizA{\displaystyle A}(llamada matriz de entrada o matriz de comunicación ) donde las filas están indexadas porincógnita∈incógnita{\displaystyle x\in X}y columnas pory∈Y{\displaystyle y\in Y}. Las entradas de la matriz sonAincógnita,y=F(incógnita,y){\displaystyle A_{x,y}=f(x,y)}Inicialmente, tanto Alice como Bob tienen una copia de toda la matriz.A{\displaystyle A}(suponiendo la funciónF{\displaystyle f}es conocido por ambas partes). Entonces, el problema de calcular el valor de la función se puede reformular como "aproximarse" a la entrada de la matriz correspondiente. Este problema se puede resolver si Alice o Bob conocen ambosincógnita{\displaystyle x}yy{\displaystyle y}. Al inicio de la comunicación, el número de opciones para la posición de la matriz correspondiente a las entradas es el tamaño de la matriz, es decir22norte{\displaystyle 2^{2n}}. Luego, a medida que cada parte comunica un poco a la otra, el número de opciones para la posición se reduce, ya que esto elimina un conjunto de filas/columnas, lo que resulta en una submatriz deA{\displaystyle A}.

Más formalmente, un conjuntoR⊆incógnita×Y{\displaystyle R\subsetequ X\times Y}se denomina rectángulo (combinatorio) si siempre que(incógnita1,y1)∈R{\displaystyle (x_{1},y_{1})\in R}y(incógnita2,y2)∈R{\displaystyle (x_{2},y_{2})\in R}entonces(incógnita1,y2)∈R{\displaystyle (x_{1},y_{2})\in R}. De forma equivalente,R{\displaystyle R}es un rectángulo combinatorio si se puede expresar comoR=METRO×norte{\displaystyle R=M\times N}para algunosMETRO⊆incógnita{\displaystyle M\subsetequ X}ynorte⊆Y{\displaystyle N\subsetequ Y}. Consideremos el caso cuandok{\displaystyle k}Ya se han intercambiado bits entre las partes. Ahora, para un caso particularh∈{0,1}k{\displaystyle h\in \{0,1\}^{k}}, definamos una matriz

Th={(incógnita,y): el k-bits intercambiados en la entrada (incógnita,y) es h}{\displaystyle T_{h}=\{(x,y):{\text{ los }}k{\text{bits intercambiados en la entrada }}(x,y){\text{ es }}h\}}

EntoncesTh⊆incógnita×Y{\displaystyle T_{h}\subsetequ X\times Y}y no es difícil demostrar queTh{\displaystyle T_{h}}es un rectángulo combinatorio enA{\displaystyle A}.

Ejemplo: EQ

Consideramos el caso en el que Alice y Bob intentan determinar si sus cadenas de entrada son iguales o no. Formalmente, definimos la función de igualdad , denotadamiQ:{0,1}norte×{0,1}norte→{0,1}{\displaystyle EQ:\{0,1\}^{n}\times \{0,1\}^{n}\rightarrow \{0,1\}}, pormiQ(incógnita,y)=1{\displaystyle EQ(x,y)=1}siincógnita=y{\displaystyle x=y}Como demostramos a continuación, cualquier solución de protocolo de comunicación deterministamiQ{\displaystyle EQ}requierenorte{\displaystyle n}fragmentos de comunicación en el peor de los casos. Como ejemplo de calentamiento, consideremos el caso simple deincógnita,y∈{0,1}3{\displaystyle x,y\in \{0,1\}^{3}}. La función de igualdad en este caso se puede representar mediante la matriz que se muestra a continuación. Las filas representan todas las posibilidades deincógnita{\displaystyle x}, las columnas las dey{\displaystyle y}.

En esta tabla, la función solo se evalúa a 1 cuandoincógnita{\displaystyle x}igualy{\displaystyle y}(es decir, en diagonal). También es bastante fácil ver cómo comunicar un solo bit divide las posibilidades de alguien por la mitad. Cuando el primer bit dey{\displaystyle y}es 1, considere solo la mitad de las columnas (dondey{\displaystyle y}puede ser igual a 100, 101, 110 o 111).

Teorema: D(EQ) = n

Prueba. Supongamos queD(miQ)≤norte−1{\displaystyle D(EQ)\leq n-1}Esto significa que existeincógnita≠incógnita′{\displaystyle x\neq x'}de tal manera que(incógnita,incógnita){\displaystyle (x,x)}y(incógnita′,incógnita′){\displaystyle (x',x')}tienen la misma transcripción de comunicaciónh{\displaystyle h}. Dado que esta transcripción define un rectángulo,F(incógnita,incógnita′){\displaystyle f(x,x')}También debe ser 1. Por definiciónincógnita≠incógnita′{\displaystyle x\neq x'}y sabemos que la igualdad solo es cierta para(a,b){\displaystyle (a,b)}cuandoa=b{\displaystyle a=b}Esto genera una contradicción.

Esta técnica para demostrar límites inferiores de comunicación determinista se denomina técnica del conjunto engañoso . [ 2 ]

Complejidad de comunicación aleatoria

En la definición anterior, nos interesa el número de bits que deben transmitirse de forma determinista entre dos partes. Si ambas partes tienen acceso a un generador de números aleatorios , ¿pueden determinar el valor deF{\displaystyle f}¿con mucha menos información intercambiada? Yao, en su artículo fundamental [ 1 ] responde a esta pregunta definiendo la complejidad de la comunicación aleatoria .

Un protocolo aleatorioR{\displaystyle R}para una funciónF{\displaystyle f}tiene un error bilateral.

Pr[R(incógnita,y)=0]>23,siF(incógnita,y)=0{\displaystyle \Pr[R(x,y)=0]>{\frac {2}{3}},{\textrm {si}}\,f(x,y)=0}
Pr[R(incógnita,y)=1]>23,siF(incógnita,y)=1{\displaystyle \Pr[R(x,y)=1]>{\frac {2}{3}},{\textrm {si}}\,f(x,y)=1}

Un protocolo aleatorio es un protocolo determinista que utiliza una cadena aleatoria adicional a su entrada habitual. Existen dos modelos: una cadena pública , que es una cadena aleatoria conocida por ambas partes de antemano, y una cadena privada , generada por una de las partes y que debe comunicarse a la otra. El teorema que se presenta a continuación demuestra que cualquier protocolo de cadena pública puede simularse mediante un protocolo de cadena privada que utiliza O(log n) bits adicionales en comparación con el original.

En las desigualdades de probabilidad anteriores, se entiende que el resultado del protocolo depende únicamente de la cadena aleatoria; ambas cadenas x e y permanecen fijas. En otras palabras, si R ( x , y ) produce g ( x , y , r ) cuando se utiliza la cadena aleatoria r , entonces g ( x , y , r ) = f ( x , y ) para al menos 2/3 de todas las elecciones para la cadena r .

La complejidad aleatoria se define simplemente como el número de bits intercambiados en dicho protocolo.

Cabe señalar que también es posible definir un protocolo aleatorio con error unilateral, y la complejidad se define de forma similar.

Ejemplo: EQ

Volviendo al ejemplo anterior de EQ , si no se requiere certeza, Alice y Bob pueden comprobar la igualdad utilizando solo ⁠O(registro⁡norte){\displaystyle O(\log n)}mensajes. Considere el siguiente protocolo: Suponga que Alice y Bob tienen acceso a la misma cadena aleatoria.z∈{0,1}norte{\displaystyle z\in \{0,1\}^{n}}Alice calculaz⋅incógnita{\displaystyle z\cdot x}y envía este fragmento (llamémoslo b ) a Bob. (El(⋅){\displaystyle (\cdot )}es el producto escalar en GF(2) .) Entonces Bob compara b conz⋅y{\displaystyle z\cdot y}Si son iguales, Bob acepta, diciendo que x es igual a y . De lo contrario, rechaza.

Claramente, siincógnita=y{\displaystyle x=y}, entoncesz⋅incógnita=z⋅y{\displaystyle z\cdot x=z\cdot y}, entoncesPAGrobz[Adodomipagt]=1{\displaystyle Prob_{z}[Aceptar]=1}. Si x no es igual a y , todavía es posible quez⋅incógnita=z⋅y{\displaystyle z\cdot x=z\cdot y}, lo que le daría a Bob la respuesta equivocada. ¿Cómo sucede esto?

Si x e y no son iguales, deben diferir en algunos puntos:

{incógnita=do1do2…pag…pag′…incógnitanortey=do1do2…q…q′…ynortez=z1z2…zi…zj…znorte{\displaystyle {\begin{cases}x=c_{1}c_{2}\ldots p\ldots p'\ldots x_{n}\\y=c_{1}c_{2}\ldots q\ldots q'\ldots y_{n}\\z=z_{1}z_{2}\ldots z_{i}\ldots z_{j}\ldots z_{n}\end{cases}}}

Donde x e y coinciden,zi∗incógnitai=zi∗doi=zi∗yi{\displaystyle z_{i}*x_{i}=z_{i}*c_{i}=z_{i}*y_{i}}Por lo tanto, esos términos afectan a los productos escalares por igual. Podemos ignorar esos términos sin problema y fijarnos solo en dónde difieren x e y . Además, podemos intercambiar los bits.incógnitai{\displaystyle x_{i}}yyi{\displaystyle y_{i}}sin cambiar si los productos escalares son iguales o no. Esto significa que podemos intercambiar bits de modo que x contenga solo ceros e y contenga solo unos:

{incógnita′=00…0y′=11…1z′=z1z2…znorte′{\displaystyle {\begin{cases}x'=00\ldots 0\\y'=11\ldots 1\\z'=z_{1}z_{2}\ldots z_{n'}\end{cases}}}

Tenga en cuenta quez′⋅incógnita′=0{\displaystyle z'\cdot x'=0}yz′⋅y′=Σizi′{\displaystyle z'\cdot y'=\Sigma _{i}z'_{i}}Ahora bien, la pregunta es: para alguna cadena aleatoriaz′{\displaystyle z'}¿Cuál es la probabilidad de que...?Σizi′=0{\displaystyle \Sigma _{i}z'_{i}=0}¿Ya que cada unozi′{\displaystyle z'_{i}}es igualmente probable que0 o1 , esta probabilidad es solo1/2{\displaystyle 1/2}. Por lo tanto, cuando x no es igual a y , PAGrobz[Adodomipagt]=1/2{\displaystyle Prob_{z}[Accept]=1/2}El algoritmo puede repetirse muchas veces para aumentar su precisión. Esto cumple con los requisitos de un algoritmo de comunicación aleatorio.

Esto demuestra que si Alice y Bob comparten una cadena aleatoria de longitud n , pueden enviarse un bit el uno al otro para calcularmiQ(incógnita,y){\displaystyle EQ(x,y)}. En la siguiente sección, se muestra que Alice y Bob solo pueden intercambiar ⁠O(registro⁡norte){\displaystyle O(\log n)}bits que son tan buenos como compartir una cadena aleatoria de longitud n . Una vez demostrado esto, se deduce que EQ se puede calcular enO(registro⁡norte){\displaystyle O(\log n)}mensajes .

Ejemplo: GH

Para otro ejemplo de complejidad de comunicación aleatoria, recurrimos a un ejemplo conocido como el problema gap-Hamming (abreviado GH ). Formalmente, Alice y Bob mantienen mensajes binarios,incógnita,y∈{−1,+1}norte{\displaystyle x,y\in \{-1,+1\}^{n}}y desean determinar si las cadenas son muy similares o si no lo son. En particular, desean encontrar un protocolo de comunicación que requiera la transmisión de la menor cantidad de bits posible para calcular la siguiente función booleana parcial:

GHnorte(incógnita,y):={−1⟨incógnita,y⟩≤norte+1⟨incógnita,y⟩≥norte.{\displaystyle {\text{GH}}_{n}(x,y):={\begin{cases}-1&\langle x,y\rangle \leq {\sqrt {n}}\\+1&\langle x,y\rangle \geq {\sqrt {n}}.\end{cases}}}

Claramente, deben comunicar todos sus bits si el protocolo ha de ser determinista (esto se debe a que, si hay un subconjunto estricto y determinista de índices que Alice y Bob se transmiten entre sí, entonces imagínese tener un par de cadenas que en ese conjunto no coinciden ennorte−1{\displaystyle {\sqrt {n}}-1}posiciones. Si surge otro desacuerdo en alguna posición que no se haya comunicado, entonces esto afecta el resultado deGHnorte(incógnita,y){\displaystyle {\text{GH}}_{n}(x,y)}y, por lo tanto, daría lugar a un procedimiento incorrecto.

Una pregunta natural que uno se hace entonces es, si se nos permite equivocarnos1/3{\displaystyle 1/3}del tiempo (en instancias aleatorias)incógnita,y{\displaystyle x,y}extraído uniformemente al azar de{−1,+1}norte{\displaystyle \{-1,+1\}^{n}}), entonces ¿podemos usar un protocolo con menos bits? Resulta que la respuesta, sorprendentemente, es no, debido a un resultado de Chakrabarti y Regev en 2012: demuestran que para instancias aleatorias, cualquier procedimiento que sea correcto al menos2/3{\displaystyle 2/3}del tiempo debe enviarΩ(norte){\displaystyle \Omega (n)}fragmentos de comunicación, es decir, prácticamente todos ellos.

Monedas públicas versus monedas privadas

La creación de protocolos aleatorios resulta más sencilla cuando ambas partes tienen acceso a la misma cadena aleatoria, lo que se conoce como protocolo de cadena compartida. Sin embargo, incluso cuando las dos partes no comparten una cadena aleatoria, es posible utilizar protocolos de cadena privada con un coste de comunicación mínimo. Cualquier protocolo aleatorio de cadena compartida que utilice cualquier número de cadenas aleatorias puede simularse mediante un protocolo de cadena privada que utiliza O(log n) bits adicionales.

Intuitivamente, podemos encontrar un conjunto de cadenas con suficiente aleatoriedad para ejecutar el protocolo aleatorio con un ligero aumento del error. Este conjunto se puede compartir de antemano, y en lugar de extraer una cadena al azar, Alice y Bob solo necesitan ponerse de acuerdo sobre qué cadena elegir del conjunto compartido. Este conjunto es lo suficientemente pequeño como para que la elección se pueda comunicar de forma eficiente. A continuación, se presenta una demostración formal .

Consideremos un protocolo aleatorio P con una tasa de error máxima de 0,1. SeaR{\displaystyle R}ser100norte{\displaystyle 100n}cadenas de longitud n , numeradasr1,r2,…,r100norte{\displaystyle r_{1},r_{2},\dots ,r_{100n}}. Dado talR{\displaystyle R}, definir un nuevo protocoloPAGR′{\displaystyle P'_{R}}que elige aleatoriamente algunosri{\displaystyle r_{i}}y luego ejecuta P usandori{\displaystyle r_{i}}como la cadena aleatoria compartida. Se necesitan O (log  100 n ) = O (log n ) bits para comunicar la elección de ri{\displaystyle r_{i}}.

Definamospag(incógnita,y){\displaystyle p(x,y)}ypagR′(incógnita,y){\displaystyle p'_{R}(x,y)}ser las probabilidades quePAG{\displaystyle P}yPAGR′{\displaystyle P'_{R}} calcular el valor correcto para la entrada(incógnita,y){\displaystyle (x,y)}.

Para un fijo(incógnita,y){\displaystyle (x,y)}Podemos usar la desigualdad de Hoeffding para obtener la siguiente ecuación:

PrR[|pagR′(incógnita,y)−pag(incógnita,y)|≥0.1]≤2exp⁡(−2(0.1)2⋅100norte)<2−2norte{\displaystyle \Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq 2\exp(-2(0.1)^{2}\cdot 100n)<2^{-2n}}

Por lo tanto, cuando no tenemos(incógnita,y){\displaystyle (x,y)}fijado:

PrR[∃(incógnita,y): |pagR′(incógnita,y)−pag(incógnita,y)|≥0.1]≤∑(incógnita,y)PrR[|pagR′(incógnita,y)−pag(incógnita,y)|≥0.1]<∑(incógnita,y)2−2norte=1{\displaystyle \Pr _{R}[\exists (x,y):\ |p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq \sum _{(x,y)}\Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]<\sum _{(x,y)}2^{-2n}=1}

La última igualdad anterior se cumple porque hay22norte{\displaystyle 2^{2n}}pares diferentes(incógnita,y){\displaystyle (x,y)}Dado que la probabilidad no es igual a 1, existe algúnR0{\displaystyle R_{0}}para que para todos(incógnita,y){\displaystyle (x,y)}:

|pagR0′(incógnita,y)−pag(incógnita,y)|<0.1{\displaystyle |p'_{R_{0}}(x,y)-p(x,y)|<0.1}

DesdePAG{\displaystyle P}tiene como máximo una probabilidad de error de 0,1,PAGR0′{\displaystyle P'_{R_{0}}}puede tener como máximo una probabilidad de error de 0,2.

Colapso de la complejidad de la comunicación aleatoria

Digamos que además permitimos que Alice y Bob compartan algún recurso, por ejemplo, un par de partículas entrelazadas. Usando ese recurso, Alice y Bob pueden correlacionar su información y así intentar "colapsar" (o "trivializar") la complejidad de la comunicación en el siguiente sentido.

Definición. Un recursoR{\displaystyle R}Se dice que está "colapsando" si, utilizando ese recursoR{\displaystyle R}, solo un poco de comunicación clásica es suficiente para que Alice conozca la evaluaciónF(incógnita,y){\displaystyle f(x,y)}en el peor de los casos para cualquier función booleanaF{\displaystyle f}.

El hecho sorprendente de un colapso de la complejidad de la comunicación es que la funciónF{\displaystyle f}Puede tener un tamaño de entrada arbitrariamente grande, pero el número de bits de comunicación sigue siendo constante a uno solo.

Se ha demostrado que algunos recursos no colapsan, como las correlaciones cuánticas [ 3 ] o, de forma más general, las correlaciones casi cuánticas [ 4 ], mientras que, por el contrario, se ha demostrado que otros recursos colapsan la complejidad de la comunicación aleatoria, como la caja PR [ 5 ] o algunas cajas PR ruidosas que satisfacen ciertas condiciones [ 6 ] [ 7 ] [ 8 ] .

Complejidad distributiva

Una forma de estudiar la complejidad de la comunicación aleatoria es mediante la complejidad distributiva.

Dada una distribución conjuntaμ{\displaystyle \mu }En función de las entradas de ambos jugadores, la complejidad distribucional correspondiente de una funciónF{\displaystyle f}es el costo mínimo de un protocolo deterministaR{\displaystyle R}de tal manera quePr[F(incógnita,y)=R(incógnita,y)]≥2/3{\displaystyle \Pr[f(x,y)=R(x,y)]\geq 2/3}donde las entradas se muestrean de acuerdo conμ{\displaystyle \mu }.

El principio minimax de Yao [ 9 ] (un caso especial del teorema minimax de von Neumann ) establece que la complejidad de comunicación aleatoria de una función es igual a su complejidad de distribución máxima, donde el máximo se toma sobre todas las distribuciones conjuntas de las entradas (¡no necesariamente distribuciones de producto!).

El principio de Yao puede utilizarse para demostrar cotas inferiores de la complejidad de comunicación aleatoria de una función: basta con diseñar la distribución conjunta adecuada y demostrar una cota inferior de la complejidad distribucional. Dado que la complejidad distribucional se refiere a protocolos deterministas, esto podría resultar más sencillo que demostrar directamente una cota inferior para protocolos aleatorios.

Como ejemplo, consideremos la función de disyunción DISJ: cada una de las entradas se interpreta como un subconjunto de{1,…,norte}{\displaystyle \{1,\dots ,n\}}y DISJ( x , y )=1 si los dos conjuntos son disjuntos. Razborov [ 10 ] demostró unΩ(norte){\displaystyle \Omega (n)}límite inferior de la complejidad de comunicación aleatoria considerando la siguiente distribución: con probabilidad 3/4, muestrear dos conjuntos disjuntos aleatorios de tamañonorte/4{\displaystyle n/4}y con probabilidad 1/4, muestrear dos conjuntos aleatorios de tamañonorte/4{\displaystyle n/4}con una intersección única.

complejidad de la información

Un enfoque poderoso para el estudio de la complejidad distribucional es la complejidad de la información. Iniciado por Bar-Yossef, Jayram, Kumar y Sivakumar, [ 11 ] el enfoque fue codificado en el trabajo de Barak, Braverman, Chen y Rao [ 12 ] y por Braverman y Rao. [ 13 ]

La complejidad de la información (interna) de un protocolo R (posiblemente aleatorio) con respecto a una distribución μ se define de la siguiente manera. Sea(incógnita,Y)∼μ{\displaystyle (X,Y)\sim \mu }sean entradas aleatorias muestreadas según μ , y sea Π la transcripción de R cuando se ejecuta sobre las entradas.incógnita,Y{\displaystyle X,Y}. La complejidad de la información del protocolo es

ICμ⁡(R)=I(Π;Y|incógnita)+I(Π;incógnita|Y),{\displaystyle \operatorname {IC} _{\mu }(R)=I(\Pi ;Y|X)+I(\Pi ;X|Y),}

donde I denota la información mutua condicional . El primer sumando mide la cantidad de información que Alice aprende sobre la entrada de Bob a partir de la transcripción, y el segundo mide la cantidad de información que Bob aprende sobre la entrada de Alice.

La complejidad de información de error ε de una función f con respecto a una distribución μ es la complejidad de información ínfima de un protocolo para f cuyo error (con respecto a μ ) es como máximo ε .

Braverman y Rao demostraron que la información equivale a la comunicación amortizada. Esto significa que el costo de resolver n copias independientes de f es aproximadamente n veces la complejidad de información de f . Esto es análogo a la conocida interpretación de la entropía de Shannon como la longitud de bits amortizada necesaria para transmitir datos desde una fuente de información determinada. La demostración de Braverman y Rao utiliza una técnica conocida como "compresión de protocolos", en la que un protocolo eficiente en información se "comprime" en un protocolo eficiente en comunicación.

Las técnicas de complejidad de la información permiten calcular la complejidad de comunicación exacta (hasta primer orden) de la disyunción de conjuntos.1.4923…norte{\displaystyle 1.4923\ldots n}. [ 14 ]

También se han utilizado técnicas de complejidad de la información para analizar formulaciones extendidas, demostrando una cota inferior esencialmente óptima en la complejidad de algoritmos basados ​​en programación lineal que resuelven aproximadamente el problema de la camarilla máxima . [ 15 ]

La encuesta de Omri Weinstein de 2015 [ 16 ] analiza el tema.

Complejidad de la comunicación cuántica

La complejidad de la comunicación cuántica intenta cuantificar la reducción de la comunicación posible mediante el uso de efectos cuánticos durante un cálculo distribuido.

Se han propuesto al menos tres generalizaciones cuánticas de la complejidad de la comunicación; para una revisión, véase el texto sugerido por G. Brassard.

El primero es el modelo de comunicación por cúbits , donde las partes pueden utilizar la comunicación cuántica en lugar de la comunicación clásica, por ejemplo, intercambiando fotones a través de una fibra óptica .

En un segundo modelo, la comunicación se sigue realizando con bits clásicos, pero las partes pueden manipular un suministro ilimitado de estados cuánticos entrelazados como parte de sus protocolos. Al realizar mediciones sobre sus estados entrelazados, las partes pueden ahorrar en comunicación clásica durante un cálculo distribuido (véase una aplicación en Colapso de la complejidad de la comunicación aleatoria ).

El tercer modelo implica el acceso a entrelazamiento previamente compartido, además de la comunicación entre cúbits , y es el menos explorado de los tres modelos cuánticos.

Complejidad de comunicación no determinista

En la complejidad de comunicación no determinista, Alice y Bob tienen acceso a un oráculo. Después de recibir la palabra del oráculo, las partes se comunican para deducirF(incógnita,y){\displaystyle f(x,y)}La complejidad de la comunicación no determinista es entonces la máxima sobre todos los pares.(incógnita,y){\displaystyle (x,y)}sobre la suma del número de bits intercambiados y la longitud de codificación de la palabra del oráculo.

Visto de otra manera, esto equivale a cubrir todas las entradas de 1 de la matriz 0/1 con rectángulos combinatorios de 1 (es decir, submatrices no contiguas y no convexas, cuyas entradas son todas de 1 (véase Kushilevitz y Nisan o Dietzfelbinger et al.)). La complejidad de comunicación no determinista es el logaritmo binario del número de rectángulos que cubren la matriz: el número mínimo de rectángulos combinatorios de 1 necesarios para cubrir todas las entradas de 1 de la matriz, sin cubrir ninguna entrada de 0.

La complejidad de la comunicación no determinista aparece como un medio para obtener cotas inferiores para la complejidad de la comunicación determinista (véase Dietzfelbinger et al.), pero también en la teoría de matrices no negativas, donde proporciona una cota inferior para el rango no negativo de una matriz no negativa . [ 17 ]

Complejidad de comunicación con errores ilimitados

En el escenario de error ilimitado, Alice y Bob tienen acceso a una moneda privada y a sus propias entradas.(incógnita,y){\displaystyle (x,y)}. En este contexto, Alice tiene éxito si responde con el valor correcto deF(incógnita,y){\displaystyle f(x,y)}con una probabilidad estrictamente mayor que 1/2. En otras palabras, si las respuestas de Alice tienen alguna correlación distinta de cero con el verdadero valor deF(incógnita,y){\displaystyle f(x,y)}, entonces el protocolo se considera válido.

Tenga en cuenta que el requisito de que la moneda sea privada es esencial. En particular, si el número de bits públicos compartidos entre Alice y Bob no se cuenta contra la complejidad de la comunicación, es fácil argumentar que calcular cualquier función tieneO(1){\displaystyle O(1)}complejidad de la comunicación. [ 18 ] Por otro lado, ambos modelos son equivalentes si se cuenta el número de bits públicos utilizados por Alice y Bob con respecto a la comunicación total del protocolo. [ 19 ]

Aunque sutiles, las cotas inferiores de este modelo son extremadamente fuertes. Más concretamente, es evidente que cualquier cota para problemas de esta clase implica inmediatamente cotas equivalentes para problemas en el modelo determinista y en los modelos de monedas privadas y públicas, pero dichas cotas también se cumplen inmediatamente para modelos de comunicación no deterministas y modelos de comunicación cuántica. [ 20 ]

Forster [ 21 ] fue el primero en demostrar cotas inferiores explícitas para esta clase, mostrando que el cálculo del producto interno⟨incógnita,y⟩{\displaystyle \langle x,y\rangle }requiere al menosΩ(norte){\displaystyle \Omega (n)}bits de comunicación, aunque un resultado anterior de Alon, Frankl y Rödl demostró que la complejidad de la comunicación para casi todas las funciones booleanasF:{0,1}norte×{0,1}norte→{0,1}{\displaystyle f:\{0,1\}^{n}\times \{0,1\}^{n}\to \{0,1\}}esΩ(norte){\displaystyle \Omega (n)}. [ 22 ]

Levantamiento

El término "lifting" es una técnica general en la teoría de la complejidad en la que se "eleva" un límite inferior de una medida simple de complejidad a un límite inferior de una medida más difícil.

Esta técnica fue desarrollada en el contexto de la complejidad de la comunicación por Raz y McKenzie, [ 23 ] quienes demostraron el primer teorema de elevación de consulta a comunicación y utilizaron el resultado para separar la jerarquía NC monótona .

Dada una funciónF:{0,1}norte→{0,1}{\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}y un aparatogramo:{0,1}a×{0,1}b→{0,1}{\displaystyle g\colon \{0,1\}^{a}\times \{0,1\}^{b}\to \{0,1\}}su composiciónF∘gramo:{0,1}nortea×{0,1}norteb→{0,1}{\displaystyle f\circ g\colon \{0,1\}^{na}\times \{0,1\}^{nb}\to \{0,1\}}se define de la siguiente manera:

(F∘gramo)(incógnita,y)=F(gramo(incógnita1,1⋯incógnita1,a,y1,1⋯y1,b),…,gramo(incógnitanorte,1⋯incógnitanorte,a,ynorte,1⋯ynorte,b)).{\displaystyle (f\circ g)(x,y)=f(g(x_{1,1}\cdots x_{1,a},y_{1,1}\cdots y_{1,b}),\dots ,g(x_{n,1}\cdots x_{n,a},y_{n,1}\cdots y_{n,b})).}

En palabras,incógnita{\displaystyle x}se divide ennorte{\displaystyle n}bloques de longituda{\displaystyle a}, yy{\displaystyle y}se divide ennorte{\displaystyle n}bloques de longitudb{\displaystyle b}El dispositivo se aplicanorte{\displaystyle n}tiempos en los bloques y las salidas se alimentan aF{\displaystyle f}. Diagramamente:

En este diagrama, cada una de las entradasincógnita1,…,incógnitanorte{\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{n}}es un poco largo, y cada una de las entradasy1,…,ynorte{\displaystyle \mathbf {y} _{1},\dots ,\mathbf {y} _{n}}tiene b bits de longitud.

Un árbol de decisiones de profundidadΔ{\displaystyle \Delta }paraF{\displaystyle f}puede traducirse a un protocolo de comunicación cuyo coste esΔ⋅D(gramo){\displaystyle \Delta \cdot D(g)}: cada vez que el árbol consulta un bit, el valor correspondiente degramo{\displaystyle g}se calcula utilizando un protocolo óptimo paragramo{\displaystyle g}. Raz y McKenzie demostraron que esto es óptimo salvo un factor constante cuandogramo{\displaystyle g}es el llamado "dispositivo de indexación", en el queincógnita{\displaystyle x}tiene longituddoregistro⁡norte{\displaystyle c\log n}(para una constante c suficientemente grande ),y{\displaystyle y}tiene longitudnortedo{\displaystyle n^{c}}, ygramo(incógnita,y){\displaystyle g(x,y)}es elincógnita{\displaystyle x}-la parte dey{\displaystyle y}.

La demostración del teorema de levantamiento de Raz-McKenzie utiliza el método de simulación, en el que se emplea un protocolo para la función compuesta.F∘gramo{\displaystyle f\circ g}se utiliza para generar un árbol de decisión paraF{\displaystyle f}. Göös, Pitassi y Watson [ 24 ] dieron una exposición de la demostración original. Desde entonces, varios trabajos han demostrado teoremas similares con diferentes artilugios, como el producto interno. [ 25 ] El artilugio más pequeño que se puede manejar es el artilugio de indexación condo=1+ϵ{\displaystyle c=1+\epsilon }. [ 26 ] Göös, Pitassi y Watson extendieron la técnica de Raz-McKenzie a protocolos aleatorizados. [ 27 ]

Una simple modificación del teorema de elevación de Raz-McKenzie proporciona una cota inferior deΔ⋅D(gramo){\displaystyle \Delta \cdot D(g)}sobre el logaritmo del tamaño de un árbol de protocolo para computaciónF∘gramo{\displaystyle f\circ g}, dóndeΔ{\displaystyle \Delta }es la profundidad del árbol de decisión óptimo paraF{\displaystyle f}Garg, Göös, Kamath y Sokolov extendieron esto al entorno tipo DAG [ 28 ] y utilizaron su resultado para obtener cotas inferiores de circuitos monótonos . La misma técnica también ha dado lugar a aplicaciones en la complejidad de las pruebas [ 29 ] .

Un tipo diferente de elevación se ejemplifica con el método de matriz de patrones de Sherstov, [ 30 ] que proporciona un límite inferior en la complejidad de la comunicación cuántica deF∘gramo{\displaystyle f\circ g}donde g es un dispositivo de indexación modificado, en términos del grado aproximado de f . El grado aproximado de una función booleana es el grado mínimo de un polinomio que aproxima la función en todos los puntos booleanos hasta un error aditivo de 1/3.

A diferencia de la prueba de Raz-McKenzie, que utiliza el método de simulación, la prueba de Sherstov toma un testigo dual para el grado aproximado de f y proporciona una cota inferior para la complejidad de consulta cuántica deF∘gramo{\displaystyle f\circ g}utilizando el método de discrepancia generalizada . El testigo dual para el grado aproximado de f es un testigo de límite inferior para el grado aproximado obtenido mediante la dualidad LP . Este testigo dual se incorpora a otros objetos que constituyen datos para el método de discrepancia generalizada.

Otro ejemplo de este enfoque es el trabajo de Pitassi y Robere, [ 31 ] en el que se eleva una brecha algebraica a una cota inferior en la medida de rango de Razborov . El resultado es una cota inferior fuertemente exponencial en la complejidad de circuito monótona de una función explícita, obtenida a través de la caracterización de Karchmer-Wigderson [ 32 ] del tamaño de circuito monótono en términos de complejidad de comunicación.

Problemas abiertos

Considerando una matriz de entrada de 0 o 1METROF=[F(incógnita,y)]incógnita,y∈{0,1}norte{\displaystyle M_{f}=[f(x,y)]_{x,y\in \{0,1\}^{n}}}, el número mínimo de bits intercambiados para calcularF{\displaystyle f}deterministamente en el peor de los casos,D(F){\displaystyle D(f)}Se sabe que está acotado inferiormente por el logaritmo del rango de la matriz.METROF{\displaystyle M_{f}}. La conjetura del rango logarítmico propone que la complejidad de la comunicación,D(F){\displaystyle D(f)}, está acotado superiormente por una potencia constante del logaritmo del rango deMETROF{\displaystyle M_{f}}Dado que D(f) está acotada superior e inferiormente por polinomios de rango logarítmico,(METROF){\displaystyle (M_{f})}Podemos decir que D(f) está relacionada polinómicamente con el logaritmo del rango.(METROF){\displaystyle (M_{f})}Dado que el rango de una matriz se puede calcular en tiempo polinomial con respecto al tamaño de la matriz, tal límite superior permitiría aproximar la complejidad de comunicación de la matriz en tiempo polinomial. Sin embargo, cabe señalar que el tamaño de la matriz en sí es exponencial con respecto al tamaño de la entrada.

Para un protocolo aleatorio, se conjeturó que el número de bits intercambiados en el peor de los casos, R(f), estaba relacionado polinómicamente con la siguiente fórmula:

registro⁡min(rango(METROF′):METROF′∈R2norte×2norte,(METROF−METROF′)∞≤1/3).{\displaystyle \log \min({\textrm {rank}}(M'_{f}):M'_{f}\in \mathbb {R} ^{2^{n}\times 2^{n}},(M_{f}-M'_{f})_{\infty }\leq 1/3).}

Estas conjeturas de rango logarítmico son valiosas porque reducen la cuestión de la complejidad de comunicación de una matriz a una cuestión de filas (columnas) linealmente independientes de la matriz. Esta versión particular, denominada Conjetura de Rango Logarítmico Aproximado, fue refutada recientemente por Chattopadhyay, Mande y Sherif (2019) [ 33 ] mediante un contraejemplo sorprendentemente simple. Esto revela que la esencia del problema de la complejidad de comunicación, por ejemplo, en el caso de EQ mencionado anteriormente, radica en determinar la posición de las entradas en la matriz para averiguar si son equivalentes.

Aplicaciones

Los límites inferiores en la complejidad de la comunicación se pueden usar para demostrar límites inferiores en la complejidad de los árboles de decisión , los circuitos VLSI , las estructuras de datos, los algoritmos de transmisión , las compensaciones espacio-temporales para las máquinas de Turing y más. [ 2 ]

Conitzer y Sandholm [ 34 ] estudiaron la complejidad de la comunicación de algunas reglas de votación comunes , esenciales en organizaciones políticas y no políticas. La complejidad de compilación es un concepto estrechamente relacionado, que puede considerarse como una complejidad de comunicación de una sola ronda.

Nayebi [ 35 ] ha estudiado la complejidad de la comunicación de los bayesianos ilimitados y limitados, estableciendo teoremas de que no hay almuerzo gratis (límites inferiores) en la alineación de la IA .

Véase también

Notas

  1. 1 2 Yao, AC ( 1979), "Algunas cuestiones de complejidad relacionadas con la computación distribuida", Actas del 11.º Simposio sobre Teoría de la Computación , 14 : 209–213
  2. 1 2 Kushilevitz, Eyal; Nisan, Noam (1997). Complejidad de la comunicación . Cambridge University Press. ISBN 978-0-521-56067-2.
  3. ↑ Cleve, Richard; Van Dam, Wim; Nielsen, Michael; Tapp, Alain (1999). «Entrelazamiento cuántico y la complejidad de la comunicación de la función de producto interno» . Computación cuántica y comunicaciones cuánticas . Notas de clase en ciencias de la computación. Vol. 1509. págs. 61–74 . doi : 10.1007/3-540-49208-9_4 . ISBN   978-3-540-65514-5. OSTI 661703 . 
  4. ↑ Navascués, Miguel; Guryanova, Yelena; Hoban, Matty J.; Acín, Antonio (2015). "Correlaciones casi cuánticas" . Comunicaciones de la naturaleza . 6 6288. arXiv : 1403.4621 . Código Bib : 2015NatCo...6.6288N . doi : 10.1038/ncomms7288 . PMID 25697645 . 
  5. ↑ W. van Dam, Nonlocality & Communication Complexity, tesis doctoral, Universidad de Oxford (1999).
  6. ↑ Brassard, Gilles; Buhrman, Harry; Linden, Noah; Méthot, André Allan; Tapp, Alain; Unger, Falk (27 de junio de 2006). "Límite de la no localidad en cualquier mundo en el que la complejidad de la comunicación no sea trivial". Physical Review Letters . 96 (25) 250401. arXiv : quant-ph/0508042 . Bibcode : 2006PhRvL..96y0401B . doi : 10.1103/PhysRevLett.96.250401 . PMID 16907289 . 
  7. ↑ Brunner, Nicolas; Skrzypczyk, Paul (24 de abril de 2009). "Destilación de no localidad y teorías postcuánticas con complejidad de comunicación trivial". Physical Review Letters . 102 (16) 160403. arXiv : 0901.4070 . Bibcode : 2009PhRvL.102p0403B . doi : 10.1103/PhysRevLett.102.160403 . PMID 19518687 . 
  8. ↑ Botteron, Pierre; Broadbent, Anne; Proulx, Marc-Olivier (14 de febrero de 2024). "Extending the Known Region of Nonlocal Boxes that Collapse Communication Complexity". Physical Review Letters . 132 (7) 070201. arXiv : 2302.00488 . Bibcode : 2024PhRvL.132g0201B . doi : 10.1103/PhysRevLett.132.070201 . PMID 38427887 . 
  9. ↑ Yao, Andrew Chi-Chih (1977). "Cálculos probabilísticos: Hacia una medida unificada de complejidad". 18º Simposio Anual sobre Fundamentos de la Informática (SFCS 1977) . IEEE. doi : 10.1109/SFCS.1977.24 . ISSN 0272-5428 . 
  10. ↑ Razborov, Alexander (1992). "Sobre la complejidad distribucional de la disyunción" . Theoretical Computer Science . 106 (2): 385– 390. doi : 10.1016/0304-3975(92)90260-M .
  11. ↑ Bar-Yossef, Ziv; Jayram, TS; Kumar, Ravi; Sivakumar, D. (2004). "Un enfoque de estadística de la información para la complejidad de la comunicación y el flujo de datos" (PDF) . Journal of Computer and System Sciences . 68 (4): 702– 732. doi : 10.1016/j.jcss.2003.11.006 . Recuperado el 1 de diciembre de 2023 .
  12. ↑ Barak, Boaz ; Braverman, Mark ; Chen, Xi; Rao, Anup (2013). "Cómo comprimir la comunicación interactiva" (PDF) . SIAM Journal on Computing . 42 (3): 1327– 1363. doi : 10.1137/100811969 .
  13. ↑ Braverman, Mark ; Rao, Anup (2014). "La información equivale a comunicación amortizada". IEEE Transactions on Information Theory . 60 (10): 6058– 6069. arXiv : 1106.3595 . doi : 10.1109/TIT.2014.2347282 .
  14. ↑ Braverman, Mark ; Garg, Ankit; Pankratov, Denis; Weinstein, Omri (junio de 2013). STOC '13: Actas del cuadragésimo quinto simposio anual de la ACM sobre Teoría de la Computación . Palo Alto, CA: ACM. págs. 151–160 . doi : 10.1145/2488608.2488628 . ISBN  978-1-4503-2029-0.
  15. ↑ Braverman, Mark ; Moitra, Ankur (1 de junio de 2013). "Un enfoque de complejidad de la información para formulaciones extendidas" . STOC '13: Actas del cuadragésimo quinto simposio anual de la ACM sobre Teoría de la Computación . Palo Alto, CA: ACM. págs. 161–170 . doi : 10.1145/2488608.2488629 . 
  16. ↑ Weinstein, Omri (junio de 2015). "Complejidad de la información y la búsqueda de la compresión interactiva" . ACM SIGACT News . 46 (2): 41– 64. doi : 10.1145/2789149.2789161 . Recuperado el 1 de diciembre de 2023 .
  17. ↑ Yannakakis, M. (1991). "Expresación de problemas de optimización combinatoria mediante programas lineales". J. Comput. Syst. Sci . 43 (3): 441– 466. doi : 10.1016/0022-0000(91)90024-y .
  18. ↑ Lovett, Shachar, CSE 291: Complejidad de la comunicación, invierno de 2019. Protocolos de error ilimitado (PDF) , consultado el 9 de junio de 2019.
  19. ↑ Göös, Mika; Pitassi, Toniann; Watson, Thomas (2018-06-01). "El panorama de las clases de complejidad de la comunicación" . Complejidad computacional . 27 (2): 245– 304. doi : 10.1007/s00037-018-0166-6 . ISSN 1420-8954 . S2CID 4333231 .  
  20. ↑ Sherstov, Alexander A. (octubre de 2008). «La complejidad de comunicación de errores no acotados de las funciones simétricas». 49.º Simposio Anual IEEE sobre Fundamentos de la Informática , 2008. págs. 384-393 . doi : 10.1109/focs.2008.20 . ISBN  978-0-7695-3436-7. S2CID 9072527 . 
  21. ↑ Forster, Jürgen (2002). "Una cota inferior lineal sobre la complejidad de comunicación probabilística de error no acotada" . Journal of Computer and System Sciences . 65 (4): 612– 625. doi : 10.1016/S0022-0000(02)00019-3 .
  22. ↑ Alon, N .; Frankl, P.; Rodl, V. (octubre de 1985). «Realización geométrica de sistemas de conjuntos y complejidad de comunicación probabilística». 26.º Simposio Anual sobre Fundamentos de la Informática (SFCS 1985) . Portland, OR, EE. UU.: IEEE. págs. 277–280 . CiteSeerX 10.1.1.300.9711 . doi : 10.1109/SFCS.1985.30 . ISBN   9780818606441. S2CID 8416636 . 
  23. ↑ Raz, Ran ; McKenzie, Pierre (1999). "Separación de la jerarquía NC monótona". Combinatorica . 19 (3): 403– 435. doi : 10.1007/s004930050062 .
  24. ↑ Göös, Mika; Pitassi, Toniann ; Watson, Thomas (2018). "Comunicación determinista frente a número de partición" . SIAM Journal on Computing . 74 (6): 2435– 2450. doi : 10.1137/16M1059369 .
  25. ↑ Chattopadhyay, Arkadev; Koucký, Michal; Loff, Bruno; Mukhopadhyay, Sagnik (2019). "Teoremas de simulación mediante propiedades pseudoaleatorias" . Computational Complexity . 28 (4): 617– 659. arXiv : 1704.06807 . doi : 10.1007/s00037-019-00190-7 .
  26. ↑ Lovett, Shachar; Meka, Raghu; Mertz, Ian; Pitassi, Toniann ; Zhang, Jiapeng (200). "Lifting with Sunflowers" (PDF) . 13.ª Conferencia sobre Innovaciones en Ciencias de la Computación Teórica (ITCS 2022) . Vol. 215. Actas Internacionales Leibniz en Informática (LIPIcs). págs. 104:1–104:24. doi : 10.4230/LIPIcs.ITCS.2022.104 .  
  27. ↑ Göös, Mika; Pitassi, Toniann ; Watson, Thomas (2017). "Query-to-Communication Lifting for BPP". 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) . Berkeley, CA: IEEE. arXiv : 1703.07666 . doi : 10.1109/FOCS.2017.21 .
  28. ↑ Garg, Ankit; Göös, Mika; Kamath, Pritish; Sokolov, Dmitry (2020). "Límites inferiores de circuitos monótonos a partir de la resolución" . Theory of Computing . 16 : 13:1–13:30. doi : 10.4086/toc.2020.v016a013 .
  29. ↑ de Rezende, Susanna; Meir, Or; Nordström, Jakob; Pitassi, Toniann ; Robere, Robere; Vinyals, Marc (2020). "Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity". 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) . Conferencia virtual: IEEE. pp. 24–30 . arXiv : 2001.02144 . doi : 10.1109/FOCS46700.2020.00011 . 
  30. ↑ Sherstov, Alexander (2011). "El método de la matriz de patrones". SIAM Journal on Computing . 40 (6): 1969– 2000. arXiv : 0906.4291 . doi : 10.1137/080733644 .
  31. ↑ Pitassi, Toniann ; Robere, Robert (2017). "Límites inferiores fuertemente exponenciales para la computación monótona" (PDF) . STOC 2017: Actas del 49.º Simposio Anual ACM SIGACT sobre Teoría de la Computación . Montreal: ACM. págs. 1246–1255 . doi : 10.1145/3055399.3055478 . 
  32. ↑ Karchmer, Mauricio; Wigderson, Avi (1990). "Los circuitos monótonos para la conectividad requieren una profundidad superlogarítmica" (PDF) . SIAM Journal on Discrete Mathematics . 3 (2): 255– 265. doi : 10.1137/0403021 .
  33. ↑ Chattopadhyay, Arkadev; Mande, Nikhil S.; Sherif, Suhail (2019). "La conjetura del rango logarítmico aproximado es falsa". 2019, Actas del 51.º Simposio Anual de la ACM sobre Teoría de la Computación: 42-53. https://doi.org/10.1145/3313276.3316353
  34. ↑ Conitzer, Vincent; Sandholm, Tuomas (5 de junio de 2005). «Complejidad de la comunicación de las reglas de votación comunes» . Actas de la 6.ª conferencia ACM sobre comercio electrónico . EC '05. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 78–87 . doi : 10.1145/1064009.1064018 . ISBN  978-1-59593-049-1.
  35. ↑ Nayebi, Aran (2025). "Barreras intrínsecas y vías prácticas para la alineación humano-IA: un análisis de complejidad basado en acuerdos". arXiv : 2502.05934 [ cs.AI ].Presentar una ponencia oral en la 40.ª Conferencia AAAI sobre Inteligencia Artificial (AAAI 2026), en la Sesión Especial sobre Alineación de IA.

Referencias

  • Rao, Anup; Yehudayoff, Amir (2020). Complejidad y aplicaciones de la comunicación . Cambridge: Cambridge University Press. ISBN 9781108671644.
  • Kushilevitz, Eyal; Nisan, Noam (2006). Complejidad de la comunicación . Cambridge: Cambridge University Press. ISBN 978-0-521-02983-4OCLC 70764786​​ 
  • Brassard, G. Complejidad de la comunicación cuántica: una revisión. https://arxiv.org/abs/quant-ph/0101005
  • Dietzfelbinger, M., J. Hromkovic, J. y G. Schnitger, " Una comparación de dos métodos de límite inferior para la complejidad de la comunicación ", Theoret. Comput. Sci. 168, 1996. 39–51.
  • Raz, Ran . «Complejidad de circuitos y comunicaciones». En Teoría de la complejidad computacional. Steven Rudich y Avi Wigderson, eds. Instituto de Estudios Avanzados de la Sociedad Matemática Americana, 2004. 129-137.
  • AC Yao, "Algunas cuestiones de complejidad relacionadas con la computación distribuida", Actas del 11.º STOC, págs.  209-213, 1979. 14
  • I. Newman, Bits aleatorios privados frente a comunes en la complejidad de la comunicación , Information Processing Letters 39, 1991, pp.  67–71.