Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #3 to TR17-128 | 27th September 2017 19:54

#### The Direct Sum of Universal Relations

Revision #3
Authors: Or Meir
Accepted on: 27th September 2017 19:54
Keywords:

Abstract:

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))$.

Changes to previous version:

Added reference to the new simple proof of Alexander Kozachinsky.

Revision #2 to TR17-128 | 28th August 2017 17:30

#### The Direct Sum of Universal Relations

Revision #2
Authors: Or Meir
Accepted on: 28th August 2017 17:30
Keywords:

Abstract:

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))$.

Changes to previous version:

Added a few remarks and clarifications.

Revision #1 to TR17-128 | 16th August 2017 00:22

#### The Direct Sum of Universal Relations

Revision #1
Authors: Or Meir
Accepted on: 16th August 2017 00:22
Keywords:

Abstract:

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))$.

### Paper:

TR17-128 | 15th August 2017 18:16

#### The Direct Sum of Universal Relations

TR17-128
Authors: Or Meir
Publication: 15th August 2017 20:37
Keywords:

Abstract:

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(s):

Comment #1 to TR17-128 | 5th September 2017 12:33

#### Comment on Meir's paper The Direct Sum of Universal Relations''

Comment #1
Authors: Alexander Kozachinsky
Accepted on: 5th September 2017 12:33
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$.