Problemas de comunicación para los cuales no se sabe que tenga un teorema determinista de suma directa

Es un viejo problema abierto si un teorema de suma directa es válido para la complejidad de comunicación determinista, es decir, si resolver instancias independientes de un problema es t veces más difícil que resolver una sola instancia. [FKNN95] mostró los siguientes resultados:$t$$t$

• Un resultado negativo: hay una función parcial (debido a [O90]) cuya complejidad de comunicación determinista es , pero calcularla en t instancias independientes tiene complejidad Θ ( t + log t ⋅ log n ) .$\Theta(\log n)$$t$$\Theta(t + \log t \cdot \log n)$
• Un resultado positivo: para cada función , si la complejidad de comunicación determinista de f es c, entonces la complejidad de calcular f en t instancias independientes es al menos Ω ( t ⋅ ( $f$$f$$c$$f$$t$.$\Omega(t \cdot (\sqrt{c} - \log n))$

No conozco ningún otro resultado positivo general sobre el problema de la suma directa. Sin embargo, parece que para problemas específicos que generalmente se consideran en la complejidad de la comunicación, por ejemplo, igualdad o desunión, se sabe que existe un teorema de suma directa.

Mi pregunta es, ¿hay otros ejemplos de problemas para los cuales un teorema de complejidad de comunicación determinista no sea conocido o no sea conocido (además de la función de [O90])?

Referencias

[FKNN95] Tomás Feder, Eyal Kushilevitz, Moni Naor, Noam Nisan: Complejidad de comunicación amortizada. SIAM J. Comput. 24 (4): 736-750 (1995)

[O90] Dos mensajes son casi óptimos para transmitir información. Alon Orlitsky. PODC, página 219-232. ACM, (1990)

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

$\Omega(n)$