Problemas de complejidad de comunicación con distancia lineal

8

¿Hay alguna complejidad de comunicación aleatorizada (no trivial) conocida con límites inferiores para problemas de brecha natural en los que las entradas 1 están linealmente lejos de las entradas 0? Es decir, funciones parciales tal que la distancia de Hamming entre cada ( x , y ) f - 1 ( 1 ) y ( x , y ) f - 1 (f:{0,1}2n{0,1,}(x,y)f1(1) es lineal, y que f requiere protocolos aleatorios para comunicarse (digamos) Ω ( (x,y)f1(0)fbits?Ω(n)

(Por ejemplo, el problema Gap-Hamming-Distance tiene distancia, mientras que estoy buscandoΩ(n)distancia; dondeGHD(x,y)=1siHD(x,y)n/2+2nΩ(n)GHD(x,y)=1 yGHD(x,y)=1siHD(x,y)n/2-HD(x,y)n/2+nGHD(x,y)=1 .)HD(x,y)n/2n

Editar : como señaló Igor, cualquier predicado de complejidad de comunicación puede convertirse en un problema con distancia lineal al requerir que las entradas sean codificadas por un buen código. Sin embargo, lo que me interesa es si existen problemas en la literatura, en los que la distancia lineal se produce de forma natural (como la distancia en el problema Gap-Hamming-Distance).

Anónimo
fuente
¿Algo como el problema booleano de coincidencia oculta encaja perfectamente? Requiere bits de comunicación (unidireccionales, aleatorizados), y parece que tiene una distancia lineal entre lasinstanciasyesyno. Ω(n)yesno
Clemente C.
(o casi lineal, supongo, ya que la entrada incluye la matriz )M
Clement C.
Gracias clemente! ¡Ese es precisamente el tipo de problemas que estaba buscando!
Anónimo
Otro problema, aunque en el modelo SMP / árbitro, es básicamente Gap-Hamming-Distance con gap lineal en (aunque las entradas x , y tienen un tamaño n log n en lugar de n ). Ver Bavarian, Gavinsky e Ito '15 , más precisamente Definición 1.9 y Teorema 1.8 (junto con el Hecho 1.4): la complejidad de la comunicación de G a p I P n en el modelo SMP con aleatoriedad privada es ˜ Ω ( nx,ynlognnGapIPn. Ω~(n)
Clemente C.

Respuestas:

6

Sea un error al corregir el código con distancia lineal. Sea g : { 0 , 1 } n × { 0 , 1 } n{ 0 , 1 } una función cuya complejidad de comunicación aleatoria es grande (digamos, Ω ( C:{0,1}n{0,1}2ng:{0,1}n×{0,1}n{0,1}oΩ(n)).Ω(n)Ω(n))

Defina para ser la función parcial que en las palabras de código de C produce f ( x , y ) = g ( C - 1 ( x ) , C - 1 ( y ) ) , y genera f:{0,1}2n×{0,1}2n{0,1,}Cf(x,y)=g(C1(x),C1(y))si al menos uno de no es en C .x,yC

Claramente, la complejidad de la comunicación de es igual a la complejidad de la comunicación de g , yf satisface la propiedad de que por cada dos entradas diferentes en las que f sale 0 o 1, la distancia entre ellas es lineal.fgff

Igor Shinkar
fuente
Gracias Igor Si bien, no hace falta decir que el problema que describe tiene una distancia lineal: estoy buscando problemas en los que la brecha se produce naturalmente (está en GHD), en lugar de artificialmente (al codificar las entradas). ¿Hay algún problema de este tipo en la literatura?
Anónimo
2

nlogn(x,M,w){0,1}2n×{0,1}n×2n×{0,1}2nMnlognyesnoΘ(n)

BHMnΩ(n)

  • [BJK04] Ziv Bar-Yossef, TS Jayram, Iordanis Kerenidis. Separación exponencial de la complejidad de comunicación unidireccional cuántica y clásica, Actas de ACM STOC 2004
  • [KR06] Iordanis Kerenidis, Ran Raz. La complejidad de comunicación unidireccional del problema de coincidencia oculta booleana. Coloquio electrónico sobre la complejidad computacional (ECCC) 13 (087) (2006)
Clemente C.
fuente