Kommunikationsprobleme, für die ein deterministischer Direktsummensatz nicht bekannt ist

Es ist ein altes offenes Problem, ob ein Direktsummensatz für die deterministische Kommunikationskomplexität gilt, dh ob das Lösen unabhängiger Instanzen eines Problems t- mal schwieriger ist als das Lösen einer einzelnen Instanz. [FKNN95] zeigte die folgenden Ergebnisse:$t$$t$

• Ein negatives Ergebnis: Es gibt eine Teilfunktion (aufgrund von [O90]), deren deterministische Kommunikationskomplexität , aber die Berechnung auf t unabhängigen Instanzen hat Komplexität Θ ( t + log t ⋅ log n ) .$\Theta(\log n)$$t$$\Theta(t + \log t \cdot \log n)$
• Ein positives Ergebnis: Wenn für jede Funktion die deterministische Kommunikationskomplexität von f c ist, beträgt die Komplexität der Berechnung von f auf t unabhängigen Instanzen mindestens Ω ( t ⋅ ( $f$$f$$c$$f$$t$.$\Omega(t \cdot (\sqrt{c} - \log n))$

Mir sind keine weiteren allgemeinen positiven Ergebnisse zum Direktsummenproblem bekannt. Es scheint jedoch, dass für bestimmte Probleme, die normalerweise in der Kommunikationskomplexität berücksichtigt werden, z. B. Gleichheit oder Disjunktheit, ein Direktsummensatz bekannt ist.

Meine Frage ist, gibt es andere Beispiele für Probleme, für die ein deterministischer Kommunikationskomplexitätssatz nicht bekannt ist oder von denen bekannt ist, dass er nicht gilt (neben der Funktion von [O90])?

Verweise:

[FKNN95] Tomás Feder, Eyal Kushilevitz, Moni Naor und Noam Nisan: Amortisierte Kommunikationskomplexität. SIAM J. Comput. 24 (4): 736 & ndash; 750 (1995)

[O90] Zwei Nachrichten sind für die Übermittlung von Informationen nahezu optimal. Alon Orlitsky. PODC, Seite 219-232. ACM (1990)

$n$$\pi_i$$S_3$$\prod_i sgn(\pi_i)$$sgn(\pi_i)$$\pi_i$

$\Omega(n)$