Skip to main content
2 of 6
added 82 characters in body
Or Meir
  • 5.7k
  • 23
  • 36

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

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 exists a partial function whose deterministic communication complexity is $\Theta(\log n)$, but computing it on $t$ independent instances has complexity $\Theta(t)$.
  • 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 [FKNN95])?

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

Or Meir
  • 5.7k
  • 23
  • 36