Batas bawah untuk Komunikasi Nondeterministic Multiparty

11

Ini adalah kelanjutan dari pertanyaan saya sebelumnya tentang komunikasi batas bawah untuk fungsi boolean parsial .

Dapatkah seseorang menyarankan referensi tentang batas bawah untuk komunikasi multi pihak non-deterministik? Saya telah mensurvei makalah di lapangan, tetapi semua orang tampaknya menunjukkan pemisahan jenis berikut: batas bawah untuk protokol acak dan batas atas (lebih kecil) untuk protokol nondeterministik. Lihat misalnya, David, Pitassi, dan Viola 2009 , Gavinsky dan Sherstov 2010 , Beame, David, Pitassi, dan Woelfel 2010 .

Secara khusus, saya ingin tahu apakah ada norma (misalnya untuk pihak ) yang lebih rendah batas komunikasi multiparty nondeterministic baik dalam model number-in-the-dahi atau number-in-hand.γkk

Marcos Villagra
sumber
haruskah saya menempatkan bagian edit sebagai jawaban dan membuat pertanyaan yang berbeda?
Marcos Villagra
Anda harus memasukkan hasil baru yang Anda temukan dalam jawaban. (mungkin Anda akan mendapatkan lencana pelajar mandiri!) Adapun masalah baru, tidak masalah untuk meninggalkannya di pertanyaan yang sama.
Hsien-Chih Chang 張顯 之
Saya pikir tidak apa-apa untuk menambahkannya sebagai jawaban. Anda mengajukan pertanyaan beberapa waktu lalu, dan menunggu jawaban. Anda kemudian menemukan satu - untuk itulah lencana pelajar mandiri
Suresh Venkat

Jawaban:

4

Setelah banyak membaca, saya menemukan makalah berikut

Troy Lee dan Adi Shraibman. Kekecewaan adalah hal yang sulit dalam model multi-partai nomor-di-dahi . Dalam Prosiding Konferensi Tahunan IEEE 23 tentang Kompleksitas Komputasi . 22-26 Juni 2008.

Para penulis menunjukkan bahwa komunikasi acak kesalahan terbatas lebih rendah dibatasi oleh norma persimpangan silinder perkiraan (lih. Definisi 5 dalam makalah).μα

Teorema 6: Misalkan M menjadi tanda -tensor, dan . Kemudian mana dan .k0ϵ<1/2Rϵk(M)log(μα(M))log(αϵ)αϵ=1/(12ϵ)ααϵ

Kemudian, mereka membuat pernyataan berikut.

Catatan 7: Sangat menyenangkan untuk dicatat bahwa karena protokol non-deterministik menginduksi penutup tensor dengan persimpangan silinder, itu mengikuti bahwa adalah batas bawah pada kompleksitas komunikasi non-deterministik.logμ

Ini menjawab pertanyaan saya. Masalahnya sekarang adalah ketika penulis menunjukkan bahwa untuk setiap matriks tanda yang diberikan , , di mana adalah perbedaan dari . Ini merupakan masalah karena batas bawah terbaik yang dapat kami buktikan menggunakan perbedaan adalah polylogaritmik dalam ukuran input. Misalnya, untuk disjointment dengan pihak batas bawah adalah . Dalam karya yang sama, penulis menunjukkan bahwa untuk protokol acak, perpisahan memerlukan menggunakan norma .M μ ( M ) = 1 / D i s c ( M ) D i s c ( M ) M k Ω ( log n / ( k - 1 ) ) Ω ( n 1 / ( k + 1 )αMμ(M)=1/Disc(M)Disc(M)MkΩ(logn/(k1))μαΩ(n1/(k+1)22k)μα

Apakah ada norma lain yang lebih kuat daripada perbedaan yang dapat digunakan untuk batas bawah dalam komunikasi multi pihak yang tidak ditentukan? Atau apakah itu ketat? Hasil ini sangat baru, jadi mungkin ini adalah masalah terbuka. Tindak lanjut dari pertanyaan ini ada di sini .

Marcos Villagra
sumber
Anda dapat menerima jawaban Anda sendiri :). juga, mungkin Anda dapat mengajukan pertanyaan baru secara terpisah?
Suresh Venkat
selesai Pertanyaan baru sekarang di cstheory.stackexchange.com/questions/3614/…
Marcos Villagra
sesaat sebelum menerimanya, saya ingin menunggu dan melihat apakah ada yang tahu batas bawah lainnya, misal teori informasi terikat
Marcos Villagra