¿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 ( es lineal, y que f requiere protocolos aleatorios para comunicarse (digamos) Ω ( √bits?
(Por ejemplo, el problema Gap-Hamming-Distance tiene distancia, mientras que estoy buscandoΩ(n)distancia; dondeGHD(x,y)=1siHD(x,y)≥n/2+ √ yGHD(x,y)=1siHD(x,y)≤n/2- √ .)
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).
Respuestas:
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}2n g:{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,∗} C f(x,y)=g(C−1(x),C−1(y)) ∗ si al menos uno de no es en C .x,y C
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.f g f f
fuente
fuente