Masalah komunikasi yang teorema jumlah-langsung deterministik tidak diketahui dimiliki

Ini adalah masalah terbuka tua apakah langsung-sum teorema berlaku untuk kompleksitas komunikasi deterministik, yaitu, apakah pemecahan contoh independen dari masalah adalah kali lebih keras dari pemecahan satu contoh. [FKNN95] menunjukkan hasil berikut:$t$$t$

• Hasil negatif: Ada fungsi parsial (karena [O90]) yang kompleksitas komunikasi deterministiknya adalah , tetapi menghitungnya pada instance independen memiliki kompleksitas .$\Theta(\log n)$$t$$\Theta(t + \log t \cdot \log n)$
• Hasil positif: Untuk setiap fungsi , jika kompleksitas komunikasi deterministik adalah maka kompleksitas komputasi pada contoh independen setidaknya .$f$$f$$c$$f$$t$$\Omega(t \cdot (\sqrt{c} - \log n))$

Saya tidak mengetahui adanya hasil positif umum lainnya pada masalah jumlah langsung. Namun, tampaknya untuk masalah-masalah khusus yang biasanya dipertimbangkan dalam kompleksitas komunikasi, misalnya kesetaraan atau ketidakberpihakan, teorema jumlah-langsung diketahui berlaku.

Pertanyaan saya adalah, apakah ada contoh lain masalah yang teorema kompleksitas komunikasi deterministiknya diketahui tidak dimiliki, atau bahkan diketahui tidak dimiliki (di samping fungsi [O90])?

Referensi:

[FKNN95] Tomás Feder, Eyal Kushilevitz, Moni Naor, Noam Nisan: Kompleksitas Komunikasi yang diamortisasi. SIAM J. Comput. 24 (4): 736-750 (1995)

[O90] Dua Pesan Hampir Optimal untuk Menyampaikan Informasi. Alon Orlitsky. PODC, halaman 219-232. ACM, (1990)

Saya pikir saya dapat menyarankan masalah, yang tidak diketahui secara luas, tapi yang aku tertarik. Misalkan kita memiliki permutasi di . Alice, Bob dan Carol masing-masing menerima elemen pertama, kedua dan ketiga dari semua permutasi. Tujuannya adalah untuk menghitung , di mana adalah tanda permutasi (dapat mengambil -1 atau +1). Saya tertarik pada kompleksitas komunikasi dalam model NiH.$n$$\pi_i$$S_3$$\prod_i sgn(\pi_i)$$sgn(\pi_i)$$\pi_i$

Beberapa waktu lalu saya sudah mencoba menerapkan teorema jumlah-langsung, tetapi di sini kita memiliki beberapa kendala dengan ketergantungan masukan dari peserta yang berbeda. Saya masih tidak tahu apakah batas bawah berlaku untuk masalah ini.$\Omega(n)$