Communication problems for which a deterministic direct-sum theorem is not known to hold

Question

It is an old open problem whether a direct-sum theorem holds for deterministic communication complexity, that is, whether solving $t$ independent instances of a problem is $t$ times harder than solving a single instance. [FKNN95] showed the following results:

• A negative result: There is partial function (due to [O90]) whose deterministic communication complexity is $\Theta(\log n)$, but computing it on $t$ independent instances has complexity $\Theta(t + \log t \cdot \log n)$.
• A positive result: For every function $f$, if the deterministic communication complexity of $f$ is $c$ then the complexity of computing $f$ on $t$ independent instances is at least $\Omega(t \cdot (\sqrt{c} - \log n))$.

I am not aware of any other general positive results on the direct-sum problem. However, it seems that for specific problems that are usually considered in communication complexity, e.g. equality or disjointness, a direct-sum theorem is known to hold.

My question is, are there other examples of problems for which a deterministic communication complexity theorem is not known to hold, or even known not to hold (beside the function of [O90])?

References:

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

[O90] Two Messages are Almost Optimal for Conveying Information. Alon Orlitsky. PODC, page 219-232. ACM, (1990)

Answer 1

I think I can suggest the problem, which is not widely known, but for which I'm interested in. Suppose we have $n$ permutations $\pi_i$ in $S_3$. Alice, Bob and Carol receive first, second and third elements of all permutations, respectively. The goal is to compute $\prod_i sgn(\pi_i)$, where $sgn(\pi_i)$ is a sign of permutation $\pi_i$ (can take -1 or +1). I'm interested in communication complexity in NiH model.

Some time ago I've tried to apply direct-sum theorem, but here we have some obstacles with dependence of input of different participants. I still don't know whether $\Omega(n)$ lower bound holds for this problem.