Month: November 2019

Introduction to Direct Sums in Communication Complexity Theory

Themistoklis Haris

The direct sum problem concerns the following question: “If a task A cannot be completed using less than c steps, then do k independent instances of task A require at least k\cdot c steps?”

In the theory of communication complexity, the task A is calculating a certain function through some form of communication.

DEFINITION

Let g\,:\,\{0,1\}^n\times\{0,1\}^n \rightarrow \{0,1\} be a function. We understand

g^k\,:\,(\{0,1\}^n)^k\times(\{0,1\}^n)^k\rightarrow\{0,1\}^k,

defined as:

g^k((x_1, . . . ,x_k),(y_1, . . . ,y_k)) = (g(x_1,y_1), . . . ,g(x_k,y_k))

to represent the task of performing k different communications with the goal of calculating g on k different inputs.

QUESTION: Is D(g^k) = kD(g)?

An easy example of a relation r for which a protocol exists that computes r^k with less communication than k times the minimum possible communication required to compute r itself is the following:

Consider the following function: Let n>0. Alice has a set S\subset [n] of size |S| = n/2. Bob has no input. The goal is Bob to produce an element of S.

One strategy we can play with is Alice sending simply her smallest element to Bob. That requires \left\lceil \log_2\left(\frac{n}{2} +1\right)\right\rceil bits, because the elements \frac{n}{2}+2, . . . , n can never be the minimum of S.

On the other hand, we require at least \left\lceil \log_2\left(\frac{n}{2} +1\right)\right\rceil bits, because if a protocol existed that somehow made Bob aware of some element in S using less than \left\lceil \log_2\left(\frac{n}{2} +1\right)\right\rceil bits for any S, then Bob would not be able to encode numbers outside of some set P \subset [n] whose cardinality is at most n/2. Thus, letting S = [n] - P breaks the protocol.

So we need exactly \left\lceil \log_2\left(\frac{n}{2} +1\right)\right\rceil bits to communicate some element of S to Bob.

Now we shall show that we can have a protocol which, given any sequence S_1, . . . , S_k \subset [n],\, |S_i| = n/2, can output a k-tuple (s_1, . . . , s_k) such that s_i \in S_i\,\forall i \in [k]. The way that protocol works is the following:

We can prove that there exists a set Q \subset [n]^k of k-tuples q = (q_1, . . . , q_k) with size |Q| = nk2^k which is such that for any sequence S_1, . . . , S_k \subset [n],\,|S_i| = n/2, there exists an element q \in Q which is such that q_i \in S_i\,\forall i \in [k]. Let us call this statement Lemma I and we will prove it below. Alice finds Q exhaustively. Alice sends Bob the name of the element of Q which works for the particular input. Overall, the cost of this communication is k + \log_2(nk) \ll k\left\lceil \log_2\left(\frac{n}{2} +1\right)\right\rceil bits of communication.

PROOF OF LEMMA

We rely on the probabilistic method. We make Q by repeating the following random experiment nk2^k times: “Choose n/2 elements from [n] by sampling each element uniformly at random.”

Given any sequence S_1, . . . , S_k \subset [n], \,|S_i| = n/2, what is the probability that for all q \in Q, there exists some i \in [k] such that q_i \notin S_i?

The probability that for some given q \in Q, we have that q_i \in S_i for all i \in [k] is (\frac{1}{2})^{k}. Therefore, the probability that for some q \in Q, at least some element misses its respective S-set is 1 - (\frac{1}{2})^{k}. So the probability that this happens for all q \in Q is

(1- (\frac{1}{2})^{k})^{|Q|} \leq e^{-(\frac{1}{2})^k|Q|}

So the probability that for all sequences S_1, . . . , S_k, the $latex Q$ we constructed misses its mark is at most 2^{nk}e^{(1/2)^k|Q|} = 2^{nk}e^{-nk} < 1 and so our proof concludes.

Next, we shall show that there is actually a lower bound to the deterministic communication cost g^k, based on the fact that we can extract a monochromatic cover for g through a monochromatic cover for g^k.

THEOREM

If g requires c bits of communication, then g^k requires at least k(\sqrt{c}-\log n - 1) bits of communication.

PROOF

We will use the following Lemma II: “If the inputs to g^k can be covered with 2^l monochromatic rectangles, then the inputs to g can be covered with \lceil 2n \cdot 2^{l/k}\rceil monochromatic rectangles.”

If we let l be the communication cost for g^k, then the inputs to g^k can be covered by 2^l monochromatic rectangles and therefore, by the Lemma above, the inputs to g can be covered by \lceil 2n \cdot 2^{l/k}\rceil rectangles, implying (*) that the computing g requires c \leq \left(\frac{l}{k} + \log n + 1\right)^2 bits communication, which finally yields that l \geq k(\sqrt{c} - log n - 1).

(*) This implication follows from a fundamental Theorem on rectangle covers, which we will not cover here for brevity, but in another post.

Now for the proof of Lemma II:

To produce a cover of g with the necessary amount of rectangles, we show that given any S \subseteq \{0,1\}^n \times \{0,1\}^n, there exists a rectangle R that is monochromatic under g and that covers at least 2^{-l/k}|S| of the inputs from S. Applying this fact repeatedly $\lceil 2n\cdot 2^{l/k}/rceil$ times, we have left at most:

2^{2n}\cdot \left(1-2^{-\frac{l}{k}}\right)^{2n\cdot 2^{l/k}} \leq 2^{2n}\cdot e^{-2^{-l/k}\cdot 2n2^{l/k}} = 2^{2n} \cdot e^{-2n} < 1

elements which are uncovered and so our statement is proved.

For the proof of the key incremental claim, we exploit the fact that (\{0,1\}^n)^k\times(\{0,1\}^n)^k can be covered by 2^l monochromatic rectangles, so that at least one “projection-rectangle” into the space \{0,1\}^n\times \{0,1\}^n has a lot of elements.

Specifically, there must exist a rectangle R' covering at least 2^{-l}|S|^k inputs from S^k. Now, project R' into its i-th coordinate by retaining only the i-th pair of inputs of Alice and Bob:

R_i = \{(x,y) \in \{0,1\}^n\times \{0,1\}^n\,:\, \exists (a,b) \in R' \rightarrow a_i = x \wedge b_i = y\}

R_i is a rectangle because R' is a rectangle, by invoking the basic rectangle-recognizability lemma and R_i is also monochromatic under g, since R' is monochromatic under g^k.

Now, we have that R' = \prod\limits_{i=1}^{k}R_i, and so

\prod\limits_{i=1}^{k}|R_i \cap S| \geq |R' \cap S| \geq 2^{-l}|S|

Thus, for some i \in [k], we much have that |R_i \cap S| \geq 2^{-l/k}|S|, which proves our claim and finishes our theorem.