Problema de Gap-Hamming

Problema en la teoría de la complejidad de la comunicación.

En la complejidad de la comunicación , el problema de brecha-Hamming pregunta, si a Alice y Bob se les da a cada uno una cadena (potencialmente diferente), cuál es el número mínimo de bits que necesitan intercambiar para que Alice calcule aproximadamente la distancia de Hamming entre sus cadenas. . La solución al problema establece aproximadamente que, si a Alice y Bob se les da una cadena a cada uno, entonces cualquier protocolo de comunicación utilizado para calcular la distancia de Hamming entre sus cadenas no funciona (asintóticamente) mejor que Bob enviando su cadena completa a Alice. Más específicamente, si a Alice y Bob se les dan cadenas de bits, no existe ningún protocolo de comunicación que permita a Alice calcular la distancia de Hamming entre sus cadenas usando menos de bits . ${\displaystyle n}$ ${\displaystyle \pm {\sqrt {n}}}$ ${\displaystyle \Omega (n)}$

El problema de brecha-Hamming tiene aplicaciones para demostrar límites inferiores para muchos algoritmos de transmisión, incluida la estimación de frecuencia de momento ^[1] y la estimación de entropía. ^[2]

Declaración formal

En este problema, Alice y Bob reciben cada uno una cadena y , respectivamente, mientras que Alice debe calcular la función (parcial), ${\displaystyle x\in \{\pm 1\}^{n}}$ ${\displaystyle y\in \{\pm 1\}^{n}}$

${\displaystyle \operatorname {GHD} (x,y)={\begin{cases}+1&D_{H}(x,y)\geq {\frac {n}{2}}+{\sqrt {n}}\\-1&D_{H}(x,y)\leq {\frac {n}{2}}-{\sqrt {n}}\\*&{\text{otherwise}},\end{cases}}}$

utilizando la menor cantidad de comunicación posible. Aquí, indica que Alice puede devolver cualquiera de y es la distancia de Hamming entre y . En otras palabras, Alice necesita devolver si la cadena de Bob es significativamente similar o significativamente diferente a la de ella y al mismo tiempo minimizar la cantidad de bits que intercambia con Bob. ${\displaystyle *}$ ${\displaystyle \pm 1}$ ${\displaystyle D_{H}(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$

La solución del problema establece que la informática requiere al menos comunicación. En particular, requiere comunicación incluso cuando y se eligen uniformemente al azar entre . ${\displaystyle \operatorname {GHD} }$ ${\displaystyle \Omega (n)}$ ${\displaystyle \Omega (n)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle \{\pm 1\}^{n}}$

Historia

El problema de la brecha-Hamming fue propuesto originalmente por Indyk y Woodruff a principios de la década de 2000, quienes inicialmente demostraron un límite inferior lineal en la complejidad de la comunicación unidireccional del problema (donde a Alice solo se le permite recibir datos de Bob) y conjeturaron un problema lineal. límite inferior en el caso general. ^[3] La cuestión del caso de ronda infinita (en el que a Alice y Bob se les permite intercambiar tantos mensajes como deseen) permaneció abierta hasta que Chakrabarti y Regev demostraron, a través de un argumento anticoncentración , que el problema general también tiene niveles inferiores lineales. complejidad limitada, resolviendo así completamente la cuestión original. ^[4] Este resultado fue seguido por una serie de otros artículos que buscaban simplificar o encontrar nuevos enfoques para demostrar el límite inferior deseado, en particular primero por Vidick ^[5] y luego por Sherstov, ^[6] y, recientemente, con una información -Aproximación teórica de Hadar, Liu, Polyanskiy y Shayevitz. ^[7]

Referencias

1. Indyk, Piotr; Woodruff, David (2005). "Aproximaciones óptimas de los momentos de frecuencia de los flujos de datos". Actas del trigésimo séptimo simposio anual de ACM sobre teoría de la informática - STOC '05 . pag. 202. doi :10.1145/1060590.1060621. ISBN 9781581139600. S2CID  7911758.
2. Chakrabarti, Amit; Cormode, Graham; McGregor, Andrés (2010). "Un algoritmo casi óptimo para estimar la entropía de una corriente". Transacciones ACM sobre algoritmos . 6 (3): 1–21. CiteSeerX 10.1.1.190.5419 . doi :10.1145/1798596.1798604. ISSN  1549-6325. S2CID  6733816. 
3. Indyk, P.; Woodruff, D. (2003). "Límites inferiores estrictos para el problema de los distintos elementos". 44º Simposio anual del IEEE sobre fundamentos de la informática, 2003. Actas . págs. 283–288. doi :10.1109/SFCS.2003.1238202. ISBN 9780769520407. S2CID  7648045.
4. Chakrabarti, Amit; Regev, Oded (2011). "Un límite inferior óptimo para la complejidad de la comunicación de la distancia-distancia". Actas del 43º simposio anual de ACM sobre teoría de la informática - STOC '11 . pag. 51. arXiv : 1009.3460 . doi :10.1145/1993636.1993644. ISBN 9781450306911. S2CID  10274326.
5. Vidick, Thomas (2012). "Una desigualdad de concentración para la superposición de un vector en un conjunto grande, con aplicación a la complejidad de la comunicación del problema brecha-Hamming-Distancia". Revista de Ciencias de la Computación Teórica de Chicago . 18 : 1–12. doi : 10.4086/cjtcs.2012.001 .
6. Sherstov, Alexander A. (17 de mayo de 2012). "La complejidad de la comunicación de la distancia Gap Hamming". Teoría de la Computación . 8 (1): 197–208. doi : 10.4086/toc.2012.v008a008 . ISSN  1557-2862.
7. Shayevitz, Ofer; Polyanskiy, Yuri; Liu, Jingbo; Hadar, Uri (25 de enero de 2019). "Complejidad de la comunicación en la estimación de correlaciones". arXiv : 1901.09100v2 [cs.IT].