Kompleksitas komunikasi deterministik vs nomor partisi

Latar Belakang:

Pertimbangkan model kompleksitas komunikasi dua pihak yang biasa digunakan di mana Alice dan Bob diberikan string bit dan dan harus menghitung beberapa fungsi Boolean , di mana . $n$ $x$ $y$ $f(x,y)$ $f:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$

Kami mendefinisikan jumlah berikut:

(kompleksitas komunikasi deterministik dari ): Jumlah bit minimum yang harus dikomunikasikan oleh Alice dan Bob untuk menghitung deterministik. $D(f)$ $f$ $f(x,y)$

(nomor partisi ): Logaritma (basis 2) dari jumlah terkecil persegi panjang monokromatik dalam partisi (atau penutup terpisah) dari . $Pn(f)$ $f$ $\{0,1\}^n \times \{0,1\}^n$

Sebuah persegi panjang monokromatik di adalah bagian sehingga mengambil nilai yang sama (yaitu, adalah monokromatik) pada semua elemen dari . $\{0,1\}^n \times \{0,1\}^n$ $R \times C$ $f$ $R \times C$

Perhatikan juga bahwa nomor partisi berbeda dari "nomor partisi protokol", yang merupakan subjek dari pertanyaan ini .

Lihat teks oleh Kushilevitz dan Nisan untuk informasi lebih lanjut. Dalam notasi mereka, apa yang telah saya definisikan sebagai adalah . $Pn(f)$ $\log_2 C^D(f)$

Catatan : Definisi-definisi ini mudah digeneralisasikan ke fungsi-fungsi non-Boolean , di mana output dari adalah beberapa set yang lebih besar. $f$ $f$

Hasil yang diketahui:

Diketahui bahwa adalah batas bawah pada , yaitu untuk semua (Boolean atau non-Boolean) , . Memang, sebagian besar teknik batas bawah (atau mungkin semua?) Untuk sebenarnya batas bawah . (Adakah yang bisa mengkonfirmasi bahwa ini berlaku untuk semua teknik batas bawah?) $Pn(f)$ $D(f)$ $f$ $Pn(f) \leq D(f)$ $D(f)$ $Pn(f)$

Diketahui juga bahwa ikatan ini paling longgar secara kuadratik (untuk fungsi Boolean atau non-Boolean), yaitu . Untuk meringkas, kita tahu yang berikut: $D(f) \leq (Pn(f))^2$

$Pn(f) \leq D(f) \leq (Pn(f))^2$

Dugaan bahwa . (Ini adalah masalah terbuka 2.10 dalam teks dengan teks oleh Kushilevitz dan Nisan.) Namun, setahu saya, pemisahan paling dikenal antara keduanya untuk fungsi Boolean hanya dengan faktor multiplikasi 2, seperti ditunjukkan dalam "The Dugaan Linear-Array dalam Kompleksitas Komunikasi Adalah Salah "oleh Eyal Kushilevitz, Nathan Linial, dan Rafail Ostrovsky. $Pn(f) = \Theta(D(f))$

Lebih tepatnya, mereka menunjukkan keluarga tak terbatas dari fungsi Boolean , sedemikian rupa sehingga . $f$ $D(f) \geq (2 - o(1)) Pn(f)$

Pertanyaan:

Apa pemisahan paling dikenal antara dan untuk fungsi-fungsi non-Boolean? Apakah masih pemisahan faktor-2 yang dirujuk di atas? $Pn(f)$ $D(f)$

Ditambahkan dalam v2 : Karena saya belum menerima jawaban dalam seminggu, saya juga senang mendengar jawaban parsial, dugaan, desas-desus, bukti anekdot, dll.

lower-bounds communication-complexity Robin Kothari
sumber

Apakah Anda yakin tentang

? Lemma 3.8 dalam buku Jukna hanya membuktikan

, dan KN hanya menyatakan

D (f) \leq (P n (f))^{2}

$D(f) \le (Pn(f))^2$

D (f) \leq 2 (P n (f))^{2}

$D(f) \le 2(Pn(f))^2$

D (f) = O ((P n (f))^{2})

$D(f) = O((Pn(f))^2)$

András Salamon

@ AndrásSalamon: Saya tidak terlalu berhati-hati menyatakan batas atas karena aku mencari fungsi lebih dekat ke batas bawah, tapi saya pikir

dicapai. Lihat Teorema 2.2 dalam "Batas Bawah dalam Kompleksitas Komunikasi" oleh Troy Lee dan Adi Shraibman.

(P n (f) + 1)^{2}

$(Pn(f)+1)^2$

Robin Kothari

Karena

, di mana

adalah jumlah daun terkecil dalam pohon protokol komunikasi untuk

, dimungkinkan untuk membuat batas bawah untuk

yang secara teknis bukan batas bawah untuk

. Namun, karena

P n (f) \leq \log L (f) \leq D (f)

$Pn(f) \le \log L(f) \le D(f)$

L (f)

$L(f)$

f

$f$

\log L (f)

$\log L(f)$

P n (f)

$Pn(f)$

, batas bawah semacam itu pada dasarnya akan membentuk perkiraan dekat dengan nilai tepat

D (f) \leq 3.4 \log L (f)

$D(f) \le 3.4\,\log L(f)$

D (f)

$D(f)$

András Salamon

Lihat juga jawaban terkait cstheory.stackexchange.com/a/3352/109

András Salamon

Jawaban:

Pertanyaan ini baru saja diselesaikan! Seperti yang saya sebutkan, diketahui bahwa

, $Pn(f) \leq D(f) \leq (Pn(f))^2$

tetapi itu adalah masalah terbuka utama untuk menunjukkan bahwa atau ada fungsi untuk . $Pn(f) = \Theta(D(f))$ $Pn(f) = o(D(f))$

Beberapa hari yang lalu ini diselesaikan oleh Mika Göös, Toniann Pitassi, Thomas Watson ( http://eccc.hpi-web.de/report/2015/050/ ). Mereka menunjukkan bahwa ada fungsi yang memuaskan $f$

. $Pn(f) = \tilde{O}((D(f))^{2/3})$

Mereka juga menunjukkan hasil yang optimal untuk versi satu sisi , yang akan saya tunjukkan dengan , di mana Anda hanya perlu menutupi 1-input dengan persegi panjang. juga memuaskan $Pn(f)$ $Pn_1(f)$ $Pn_1(f)$

, $Pn_1(f) \leq D(f) \leq (Pn_1(f))^2$

dan mereka menunjukkan bahwa ini adalah hubungan terbaik antara kedua ukuran, karena mereka menunjukkan fungsi yang memuaskan $f$

. $Pn_1(f) = \tilde{O}((D(f))^{1/2})$

Robin Kothari
sumber

Ini dengan baik mengakhiri pertanyaan!

András Salamon

Anda berkomentar bahwa batas bawah pada terkait erat dengan semua teknik batas bawah yang ada. Untuk fungsi Boolean ini tampaknya benar, selama dugaan log-rank benar. Namun, dapat secara eksponensial lebih besar daripada ikatan yang ditetapkan yang menipu. $Pn(f)$ $Pn(f)$

Tidak jelas bagi saya berapa banyak dan dapat berbeda dalam kasus non-Boolean. $Pn(f)$ $D(f)$

Selanjutnya saya membuat komentar ini lebih tepat.

KN (Kushilevitz dan Nisan dalam buku teks 1997 mereka) menguraikan tiga teknik dasar untuk fungsi Boolean: ukuran satu set bodoh, ukuran persegi panjang monokromatik, dan pangkat matriks komunikasi.

$S$ $z \in \{0,1\}$ $f(x,y) = z$ $(x,y)\in S$ $f \colon X \times Y \to \{0,1\}$ $(x_1,y_1),(x_2,y_2) \in X \times Y$ $f$ $f(x_1,y_1) = f(x_2,y_2)$ $f(x_1,y_2) \ne f(x_1,y_1)$ $f(x_2,y_1) \ne f(x_1,y_1)$ $S \subseteq X \times Y$ $f$ $S$

$s$ $S$ $R_s$ $R$ $S$ $R$ $S$ $S$ $n$ $1/4$ $n$ $Pn(f) = n$ $O(\log n)$

$a> 0$ $Pn(f) \le a\log rk(f)$ $f$ $D(f) \le (2a\log rk(f))^2$ $rk(f)$ $|X|+|Y|$ $2+\epsilon$ $\epsilon > 0$ $|X|+|Y|$ $c>0$ $D(f) \le (\log rk(f))^c$ $f$ $rk(f)$ $f$

Demikian pula, jika hanya ada satu persegi panjang monokromatik yang cukup besar bersama dengan banyak yang kecil, maka nomor partisi memberikan ikatan yang lebih kuat daripada ukuran log dari persegi panjang monokromatik terbesar. Namun, dugaan log-rank juga setara dengan dugaan tentang ukuran persegi panjang monokromatik terbesar (Nisan dan Wigderson 1995, doi: 10.1007 / BF01192527 , Teorema 2). Jadi menggunakan persegi panjang monokromatik saat ini tidak diketahui "sama dengan" menggunakan nomor partisi, tetapi mereka terkait erat jika dugaan log-rank berlaku.

Singkatnya, ukuran log dari set pembodohan lemah terbesar mungkin secara eksponensial lebih kecil dari jumlah partisi. Mungkin ada kesenjangan antara teknik batas bawah lainnya dan nomor partisi, tetapi jika dugaan log-rank berlaku maka kesenjangan ini kecil.

Dengan menggunakan gagasan ukuran yang memperpanjang yang biasa (kardinalitas), ukuran persegi panjang monokromatik apa pun dapat digunakan untuk menggeneralisasi perangkat yang menipu, dan untuk membatasi kompleksitas komunikasi (lihat KN 1.24). Saya tidak yakin seberapa dekat "ukuran" terbesar umum dari persegi panjang monokromatik dengan kompleksitas komunikasi.

$D(f)$ $\log rk(f)$ $f$ $\log n$ $3^n$ $D(f) \ge Pn(f) \ge (2 - \log 3)n > 0.4n$ $D(f)$ $Pn(f)$ $2.5$ $Pn(f)$ $D(f)$ $f$

$Pn(f)$

András Salamon
sumber

P n (f)

$Pn(f)$

D (f)

$D(f)$

D (f)

$D(f)$

P n (f)

$Pn(f)$

D (f) \geq P n (f) \geq 2 n - \log m o n o (f)

$D(f) \ge Pn(f) \ge 2n - \log mono(f)$

m o n o (f)

$mono(f)$

f

$f$

f

$f$

2^{n} \times 2^{n}

$2^n\times 2^n$ . Komentar saya adalah tentang seberapa dekat ketidaksetaraan ini, misalnya apakah mereka menghindari kesenjangan eksponensial, dan mengapa ukuran himpunan pembodohan yang lemah lebih berguna daripada gagasan biasa (versi monokromatik dapat secara eksponensial lebih kecil daripada batas peringkat).

András Salamon