ECCC-Report TR17-128https://eccc.weizmann.ac.il/report/2017/128Comments and Revisions published for TR17-128en-usWed, 27 Sep 2017 19:54:16 +0300
Revision 3
| The Direct Sum of Universal Relations |
Or Meir
https://eccc.weizmann.ac.il/report/2017/128#revision3The 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))$.Wed, 27 Sep 2017 19:54:16 +0300https://eccc.weizmann.ac.il/report/2017/128#revision3
Comment 1
| Comment on Meir's paper ``The Direct Sum of Universal Relations'' |
Alexander Kozachinsky
https://eccc.weizmann.ac.il/report/2017/128#comment1In \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$.
Tue, 05 Sep 2017 12:33:08 +0300https://eccc.weizmann.ac.il/report/2017/128#comment1
Revision 2
| The Direct Sum of Universal Relations |
Or Meir
https://eccc.weizmann.ac.il/report/2017/128#revision2The 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))$.Mon, 28 Aug 2017 17:30:03 +0300https://eccc.weizmann.ac.il/report/2017/128#revision2
Revision 1
| The Direct Sum of Universal Relations |
Or Meir
https://eccc.weizmann.ac.il/report/2017/128#revision1The 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))$.Wed, 16 Aug 2017 00:22:48 +0300https://eccc.weizmann.ac.il/report/2017/128#revision1
Paper TR17-128
| The Direct Sum of Universal Relations |
Or Meir
https://eccc.weizmann.ac.il/report/2017/128The 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))$.Tue, 15 Aug 2017 20:37:03 +0300https://eccc.weizmann.ac.il/report/2017/128