Kompleksitas komunikasi terbaik batas bawah dari ketidakteraturan

14

Telah diketahui secara umum bahwa tidak ada protokol dua pihak deterministik yang dapat menyelesaikan masalah disjointness (DISJ) pada input bit tanpa mengirim bit dalam kasus terburuk (lihat, misalnya, buku oleh Kushilevitz dan Nisan). Untuk protokol acak terbatas kesalahan, batas bawah , untuk beberapa konstanta , juga telah ditunjukkan dalam makalah seminal oleh Razborov [Razborov92]. Pertanyaanku adalah:nn+1δnδ

Apa nilai eksplisit paling dikenal dari saat ini (baik batas atas dan bawah)?δ

Juga, apakah ada kepercayaan pada nilai aktual ?δ

[Razborov92] Alexander A. Razborov: Tentang Kompleksitas Distribusi Ketidakjelasan. Teor Komputasi. Sci. 106 (2): 385-390 (1992) doi: 10.1016 / 0304-3975 (92) 90260-M

Danu
sumber
7
Apakah Anda mengetahui konten makalah ini? eccc.hpi-web.de/report/2012/171 . Para penulis menghitung δ persis seperti beberapa konstanta di dekat 0,4827.
Yonatan N
2
@Yonatan Buat itu jawaban?
Yuval Filmus
@YonatanN Saya tidak mengetahui makalah ini. Terima kasih banyak untuk penunjuknya!
Danu
4
Hati-hati, n +1 adalah untuk protokol deterministik dan mudah dibuktikan, makalah selanjutnya adalah untuk acak!
domotorp

Jawaban:

16

Dalam makalah baru-baru ini , Braverman, Garg, Pankratov, dan Weinstein menghitung nilai menjadi beberapa konstanta di sekitar 0,4827, hingga faktor sublinear. Ini memberikan ikatan ketat pada kompleksitas komunikasi disjointness.δ

Konstanta itu sendiri ditemukan menggunakan sistem aljabar komputer, dan sejauh yang saya ketahui tidak dapat diungkapkan dengan sederhana.

Yonatan N
sumber