The Direct Sum of Universal Relations

by Or Meir

Oded's comments

Understanding the direct-sum of KW-communication problems seems a preliminary step toward understanding composition in that model, where such composition results promise a way towards new circuit depth (uquiv., formula size) lower bounds. Recall that KW-communication problems are search problems in which one party is given an input in one predetermined set (i.e., the set of premages of 1 under a predetermined Boolena function), the other party is given an input in the complementary set, and their task is to find an index on which their inputs differ.

But before trying to prove direct-sum theorems for KW-communication problems, what about the direct-sum of the universal relation (in which the parties are just given diffent inputs)? Amazingly enough, it seems that this basic question was not asked before. The current work asks this question and answers (modulo a displeasing logarithmic term).

Clarifaction: My strating sentence should not be understood as a claim that, in the context of KW-communication problems, direct-sum results are known to be easier than composition results. It is only that they appear so to me; that is, I believe that they are and should be morally easier.

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

See ECCC TR17-128.


Back to list of Oded's choices.