Nol kesalahan kompleksitas komunikasi acak vs kompleksitas komunikasi deterministik

Diketahui bahwa untuk kesalahan definisi kasus terburuk dari kompleksitas komunikasi acak dan definisi kasus rata-rata adalah setara. Tetapi ketika kesalahannya adalah , kompleksitas komunikasi acak kasus terburuk sama dengan kompleksitas komunikasi deterministik. $\Theta(1)$ $0$

Apakah ada fungsi yang diketahui memiliki kompleksitas komunikasi deterministik super-konstan tetapi konstan nol kesalahan kompleksitas komunikasi acak?

Secara umum, apa fungsi saksi yang memisahkan kompleksitas komunikasi deterministik dan kompleksitas komunikasi acak nol kesalahan?

Bantuan apa pun dihargai.

communication-complexity sagnik
sumber

Maksud Anda sebaliknya (acak kecil, tetapi deterministik besar)?

Noam

Ya, sangat menyesal atas kekacauan itu. Saya ingin konstan kompleksitas komunikasi acak nol-kesalahan tetapi kompleksitas komunikasi deterministik super konstan. Saya sedang mencari masalah

set disjointness. Karena

dan protokol Hastad-Wigderson sudah memberikan protokol satu sisi untuk

-set disjointness dari biaya

k

$k$

R_{0} (f) = O (m a x {R^{1} (f), R^{1} (not f)})

$R_0(f)=O(max\{R^1(f), R^1(\text{not }f)\})$

k

$k$

O (k)

$O(k)$ masalah bermuara untuk membuktikan biaya konstan acak-kesalahan satu sisi batas atas untuk tidak-k-set-disjointness. Apakah sudah ada hasilnya?

sagnik

Nol kesalahan kompleksitas komunikasi acak vs kompleksitas komunikasi deterministik

Jawaban: