<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-05-19T18:23:12.003Z
2015-05-19T18:23:12.003Z
Vsevolod Oparin
<p>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:</p>

<ul>
<li><strong>A negative result:</strong> 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)$.</li>
<li><strong>A positive result:</strong> 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))$.</li>
</ul>

<p>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.</p>

<p>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])?</p>

<p><strong>References:</strong></p>

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

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

<cc.complexity-theory><communication-complexity>
Communication problems for which a deterministic direct-sum theorem is not known to hold
Or Meir
# Communication problems for which a deterministic direct-sum theorem is not known to hold

(Asked by: username_0 on 2015-05-18)

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)

**Tags:** cc.complexity-theory, communication-complexity


---

## 1 answers

### Answer by username_1 on 2015-05-19. Score: 5

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.


---

