Problèmes de communication pour lesquels un théorème déterministe à somme directe n'est pas connu

$t$$t$

• $\Theta(\log n)$$t$$\Theta(t + \log t \cdot \log n)$
• $f$$f$$c$$f$$t$$\Omega(t \cdot (\sqrt{c} - \log n))$

Je ne connais aucun autre résultat général positif sur le problème de la somme directe. Cependant, il semble que pour des problèmes spécifiques qui sont généralement pris en compte dans la complexité de la communication, par exemple l'égalité ou la disjonction, un théorème à somme directe soit connu.

Ma question est, y a-t-il d'autres exemples de problèmes pour lesquels un théorème déterministe de la complexité de la communication n'est pas connu, ou même connu pour ne pas tenir (à côté de la fonction de [O90])?

Références:

[FKNN95] Tomás Feder, Eyal Kushilevitz, Moni Naor, Noam Nisan: Amortized Communication Complexity. SIAM J. Comput. 24 (4): 736-750 (1995)

[O90] Deux messages sont presque optimaux pour transmettre des informations. Alon Orlitsky. PODC, pages 219-232. ACM, (1990)

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

$\Omega(n)$