Melhor complexidade de comunicação, limite inferior de disjunção

14

É sabido que nenhum protocolo determinístico de duas partes pode resolver o problema de disjunção (DISJ) em entradas de bits sem enviar n + 1 bits no pior caso (consulte, por exemplo, o livro de Kushilevitz e Nisan). Para delimitada-randomizados erro protocolos, um limite inferior de δ n , para alguns constante δ , também tem sido demonstrado em um papel seminal por Razborov [Razborov92]. Minha pergunta é:nn+1δnδ

Qual é o valor explícito mais conhecido de atualmente (limites superior e inferior)?δ

Além disso, existe alguma crença no valor real de ?δ

[Razborov92] Alexander A. Razborov: Sobre a complexidade distributiva da disjunção. Theor. Comput. Sci. 106 (2): 385-390 (1992) doi: 10.1016 / 0304-3975 (92) 90260-M

Danu
fonte
7
Você está ciente do conteúdo deste artigo recente? eccc.hpi-web.de/report/2012/171 . Os autores calculam δ exatamente como uma constante próxima de 0,4827.
Página
2
@Yonatan Tornar isso uma resposta?
Yuval Filmus
@YonatanN Não conheço este artigo recente. Muito obrigado pelo ponteiro!
Danu
4
Tenha cuidado, n + 1 é para protocolos determinísticos e fácil de provar, trabalhos posteriores são para randomização!
Domotorp

Respostas:

16

Em um artigo recente , Braverman, Garg, Pankratov e Weinstein calculam o valor de como exatamente uma constante em torno de 0,4827, até fatores sublineares. Isso dá um estreito vínculo com a complexidade de comunicação da disjunção.δ

A constante em si foi encontrada usando um sistema de álgebra computacional e, até onde sei, não pode ser expressa de maneira simples.

Yonatan N
fonte