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