Mejor complejidad de comunicación, límite inferior de desunión

14

Es bien sabido que no existe un protocolo determinista de dos partes puede resolver el problema de disyunción (DISJ) en entradas -bit sin enviar bits en el peor de los casos (véase, por ejemplo, el libro de Kushilevitz y Nisan). Para protocolos aleatorios de error acotado, Razborov [Razborov92] también ha mostrado un límite inferior de , para alguna constante . Mi pregunta es:nortenorte+1δnorteδ

¿Cuál es el valor explícito más conocido de actualmente (límites superior e inferior)?δ

Además, ¿hay alguna creencia en el valor real de ?δ

[Razborov92] Alexander A. Razborov: Sobre la complejidad distributiva de la desunión. Theor Comput Sci. 106 (2): 385-390 (1992) doi: 10.1016 / 0304-3975 (92) 90260-M

Danu
fuente
77
¿Conoces el contenido de este artículo reciente? eccc.hpi-web.de/report/2012/171 . Los autores calculan δ exactamente como alguna constante cerca de 0.4827.
Yonatan N
2
@Yonatan ¿Eso es una respuesta?
Yuval Filmus el
@YonatanN No estoy al tanto de este artículo reciente. Muchas gracias por el puntero!
Danu
44
Tenga cuidado, n + 1 es para protocolos deterministas y fácil de probar, ¡los trabajos posteriores son aleatorios!
domotorp

Respuestas:

16

δ

La constante misma se encontró usando un sistema de álgebra computacional, y que yo sepa, no se puede expresar simplemente.

Yonatan N
fuente