Loading jsMath...
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 #3 to TR17-128 | 27th September 2017 19:54

The Direct Sum of Universal Relations

RSS-Feed




Revision #3
Authors: Or Meir
Accepted on: 27th September 2017 19:54
Downloads: 763
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
Downloads: 996
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: 1090
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: 1109
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: 1048
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