Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874172 | Information Processing Letters | 2018 | 7 Pages |
Abstract
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â
(nâO(logâ¡m)).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Or Meir,