The universal relation is the communication problem in which Alice and Bob get as inputs two distinct strings, and they are required to find a coordinate on which the strings differ. The study of this problem is motivated by its connection to Karchmer-Wigderson relations, which are communication problems that are tightly related to circuit-depth lower bounds.

In this paper, we prove a direct sum theorem for the universal relation, namely, we prove that solving $m$ independent instances of the universal relation is $m$ times harder than solving a single instance. More specifically, it is known that the deterministic communication complexity of the universal relation is at least $n$. We prove that the deterministic communication complexity of solving $m$ independent instances of the universal relation is at least $m \cdot (n-O(\log m))$.

Added a few remarks and clarifications.

The universal relation is the communication problem in which Alice and Bob get as inputs two distinct strings, and they are required to find a coordinate on which the strings differ. The study of this problem is motivated by its connection to Karchmer-Wigderson relations, which are communication problems that are tightly related to circuit-depth lower bounds.

In this paper, we prove a direct sum theorem for the universal relation, namely, we prove that solving $m$ independent instances of the universal relation is $m$ times harder than solving a single instance. More specifically, it is known that the deterministic communication complexity of the universal relation is at least $n$. We prove that the deterministic communication complexity of solving $m$ independent instances of the universal relation is at least $m \cdot (n-O(\log m))$.

The universal relation is the communication problem in which Alice and Bob get as inputs two distinct strings, and they are required to find a coordinate on which the strings differ. The study of this problem is motivated by its connection to Karchmer-Wigderson relations, which are communication problems that are tightly related to circuit-depth lower bounds.

In this paper, we prove a direct sum theorem for the universal relation, namely, we prove that solving $m$ independent instances of the universal relation is $m$ times harder than solving a single instance. More specifically, it is known that the deterministic communication complexity of the universal relation is at least $n$. We prove that the deterministic communication complexity of solving $m$ independent instances of the universal relation is at least $m \cdot (n-O(\log m))$.

Comment #1 Authors: Alexander Kozachinsky

Accepted on: 5th September 2017 12:33

Downloads: 36

Keywords:

In \cite{meir2017the} Meir proved that deterministic communication complexity of the $m$-fold direct sum of the universal relation is at least $m(n - O(\log m))$. In this comment we present a log-rank argument which improves Meir's lower bound to $m(n - 1) - 1$.