Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

The Direct Sum of Universal Relations

RSS-Feed




Revision #2
Authors: Or Meir
Accepted on: 28th August 2017 17:30
Downloads: 49
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
Downloads: 150
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
Downloads: 109
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
Downloads: 36
Keywords: 


Abstract:

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




ISSN 1433-8092 | Imprint