Communication complexity

In theoretical informatics, communication complexity studies the amount of communication needed to solve a problem whose parameters are distributed between two or more parties. This concept was introduced by Andrew Yao in 1979 ^[1] , who investigated the following problem for two participants, traditionally called Alice and Bob . Alice receives an n- bit string x, and Bob receives an n -bit string y , and their goal is for one of them (for example, Bob) to calculate a function known and known to both participants $f(x,y)$ ${\ displaystyle f (x, y)}$ $f (x, y)$ , with the least amount of communication between them. Of course, they can always calculate $f(x,y)$ ${\ displaystyle f (x, y)}$ $f (x, y)$ as follows: Alice sends all of her n-bit string to Bob, which then evaluates the function $f(x,y)$ ${\ displaystyle f (x, y)}$ $f (x, y)$ . Therefore, in this statement of the problem, it is interesting for what functions f there is a way to calculate $f(x,y)$ ${\ displaystyle f (x, y)}$ $f (x, y)$ passing less than n bits. It is important to note that in this problem we are not interested in the complexity of the calculations performed by Alice or Bob, or the size of the memory used for these calculations.

This abstract problem with two participants (called communication complexity with two participants) and its general form with a large number of participants occurs in various fields of computer science: for example, when designing circuits of large integrated circuits, it is necessary to minimize the energy used by reducing the number of electrical signals between different components during distributed computing. Communication complexity is also used in the study of data structures and algorithms, in the optimization of computer networks, in the theory of computational complexity and complexity of evidence, and in other areas.

Formal Definition

Let some function be given initially $f:X\times Y\to Z$ ${\ displaystyle f: X \ times Y \ to Z}$ $f:X\times Y\to Z$ where in the most typical setting $X=Y=\{0,1\}^{n},Z=\{0,1\}$ ${\ displaystyle X = Y = \ {0,1 \} ^ {n}, Z = \ {0,1 \}}$ $X=Y=\{0,1\}^{n},Z=\{0,1\}$ . Alice gets the item $x\in X$ ${\ displaystyle x \ in X}$ $x\in X$ Bob gets $y\in Y$ ${\ displaystyle y \ in Y}$ $y\in Y$ . By exchanging messages with each other on one bit (using some predefined communication protocol ), Alice and Bob want to calculate the value $z=f(x,y)$ ${\ displaystyle z = f (x, y)}$ $z=f(x,y)$ so that at the end of the conversation at least one of them knows the meaning $z$ ${\ displaystyle z}$ $z$ .

Communication complexity of function calculation $f$ ${\ displaystyle f}$ $f$ are designated $D(f)$ ${\ displaystyle D (f)}$ $D(f)$ , is defined as the minimum number of bits of communication, which is enough to solve the problem in the worst case (that is, this number of bits should be enough for any pair $x, y$ ${\ displaystyle x, y}$ $x,y$ )

Based on this definition, it is convenient to think of the function f as a function given by the matrix A in which the rows are indexed by elements $x\in X$ ${\ displaystyle x \ in X}$ $x\in X$ , and columns, respectively, by elements $y\in Y$ ${\ displaystyle y \ in Y}$ $y\in Y$ . In each cell of this matrix indexed by the elements x and y , the corresponding value of f is written, i.e. $A_{\mathrm {x,y} }=f(x,y)$ ${\ displaystyle A _ {\ mathrm {x, y}} = f (x, y)}$ $A_{\mathrm {x,y} }=f(x,y)$ . Alice and Bob know the function f , and therefore they know the matrix A. Next, Alice is given the row number x , and Bob is given the column number y , and their task is to determine the value written in the corresponding cell. Therefore, if at some point one of the players knows both the column number and the line number, then he will know the value in the corresponding cell. At the beginning of communication, each player does not know anything about the number of the other player, so from the point of view of Alice, the answer can be any value in the line with number x , and from the point of view of Bob, any value in the column y . In the process of communication with each transmitted bit, new information appears, which allows players to cut off part of the possible cells. For example, if at some point Alice transmits bit b , then from Bob’s point of view all Alice’s possible inputs at that moment are divided into two sets: those for which Alice would send $b=0$ ${\ displaystyle b = 0}$ , and those for whom Alice would send $b=1$ ${\ displaystyle b = 1}$ . Knowing the value of bit b, Bob cuts off part of Alice's possible inputs and thus narrows the set of cells possible from his point of view. Moreover, from the point of view of the external observer, after each message, either the set of possible rows or the set of possible columns narrows, and thus the set of possible cells narrows to some submatrix of matrix A.

More formally, we will call the set $R\subseteq X\times Y$ ${\ displaystyle R \ subseteq X \ times Y}$ is called a (combinatorial) rectangle if from $(x_{1},y_{1})\in R$ ${\ displaystyle (x_ {1}, y_ {1}) \ in R}$ and $(x_{2},y_{2})\in R$ ${\ displaystyle (x_ {2}, y_ {2}) \ in R}$ , follows that $(x_{1},y_{2})\in R$ ${\ displaystyle (x_ {1}, y_ {2}) \ in R}$ and $(x_{2},y_{1})\in R$ ${\ displaystyle (x_ {2}, y_ {1}) \ in R}$ . Then each submatrix of A is associated with a combinatorial rectangle R such that $R=M\times N$ ${\ displaystyle R = M \ times N}$ where $M\subseteq X$ ${\ displaystyle M \ subseteq X}$ and $N\subseteq Y$ ${\ displaystyle N \ subseteq Y}$ . Now consider a situation where k bits have already been transmitted between participants. Let these first k bits be given as a string $h\in \{0,1\}^{k}$ ${\ displaystyle h \ in \ {0,1 \} ^ {k}}$ . Then you can define many pairs of inputs $T_{\mathrm {h} }\subseteq X\times Y$ ${\ displaystyle T _ {\ mathrm {h}} \ subseteq X \ times Y}$ on which the first k are equal $h$ ${\ displaystyle h}$

T_{\mathrm {h} }=\{(x,y):k

{\ displaystyle T _ {\ mathrm {h}} = \ {(x, y): k}

-bit communication at the inputs

(x,y)

{\ displaystyle (x, y)}

is equal to

h\}

{\ displaystyle h \}}

Then $T_{\mathrm {h} }$ ${\ displaystyle T _ {\ mathrm {h}}}$ is a combinatorial rectangle, that is, it defines a submatrix of the matrix A.

Example: EQ Function

Let be $X=Y=\{0,1\}^{n},Z=\{0,1\}$ ${\ displaystyle X = Y = \ {0,1 \} ^ {n}, Z = \ {0,1 \}}$ . Consider a problem in which Alice and Bob want to determine if they are given the same lines, that is, they want to check that $x=y$ ${\ displaystyle x = y}$ . It is easy to show that to solve this problem of checking equality (EQ), you need to transfer n bits in the worst case, if we want to be able to learn how to answer this question exactly for all possible pairs x and y .

For case $n=3$ ${\ displaystyle n = 3}$ strings x and y consist of three bits. The equality function in this case is determined by the following matrix, in which the rows are indexed by Alice's inputs, and the rows are indexed by Bob's entries.

Eq	000	001	010	011	100	101	110	111
000	one	0	0	0	0	0	0	0
001	0	one	0	0	0	0	0	0
010	0	0	one	0	0	0	0	0
011	0	0	0	one	0	0	0	0
100	0	0	0	0	one	0	0	0
101	0	0	0	0	0	one	0	0
110	0	0	0	0	0	0	one	0
111	0	0	0	0	0	0	0	one

As we can see, the function $E Q$ ${\ displaystyle EQ}$ equals 1 only in cells where x is equal to y (i.e., on the diagonal).

Theorem: $D(EQ)=n$ ${\ displaystyle D (EQ) = n}$

Evidence. Let's pretend that $D(EQ)\leq n-1$ ${\ displaystyle D (EQ) \ leq n-1}$ , that is, there is a protocol that solves the problem of checking equality for all pairs of bit strings of length n , transmitting no more than $n-1$ ${\ displaystyle n-1}$ bit. Let’s for each possible pair of identical lines $(x,x)$ ${\ displaystyle (x, x)}$ (for them $EQ(x,x)=1$ ${\ displaystyle EQ (x, x) = 1}$ ) write in the line all the bits that were sent in the protocol. Total of such various pairs $(x,x)$ ${\ displaystyle (x, x)}$ smooth $2^{n}$ ${\ displaystyle 2 ^ {n}}$ , and various bit strings of length no more than $n-1$ ${\ displaystyle n-1}$ Total $2+4+\dotsb +2^{n-1}=2^{n}-2<2^{n}$ ${\ displaystyle 2 + 4 + \ dotsb + 2 ^ {n-1} = 2 ^ {n} -2 <2 ^ {n}}$ . By the Dirichlet principle, there are two pairs $(x,x)$ ${\ displaystyle (x, x)}$ and $(x',x')$ ${\ displaystyle (x ', x')}$ for which the same lines were obtained, that is, the same bits were sent in the protocol. Since many pairs of strings for which identical bits were sent sets a rectangle, then $EQ(x,x')$ ${\ displaystyle EQ (x, x ')}$ and $EQ(x',x)$ ${\ displaystyle EQ (x ', x)}$ must also be equal to 1, which contradicts the fact that $x\neq x'$ ${\ displaystyle x \ neq x '}$ . Therefore, our assumption is false, which means $D(EQ)>n-1$ ${\ displaystyle D (EQ)> n-1}$

In other words, if $D(EQ)$ ${\ displaystyle D (EQ)}$ less than n , then we must be able to cover all the units of the matrix EQ with less $2^{n}$ ${\ displaystyle 2 ^ {n}}$ solid rectangles (all cells of which are marked with units). However, in the matrix EQ exactly $2^{n}$ ${\ displaystyle 2 ^ {n}}$ one, and no two can lie in the same monochrome rectangle, since then cells marked with zeros will inevitably get into this rectangle. Therefore, such coverage does not exist, which means $D(EQ)$ ${\ displaystyle D (EQ)}$ at least n .

Notes

↑ Yao, AC (1979), "Some Complexity Questions Related to Distributed Computing", Proc. of 11th STOC T. 14: 209–213

Literature

Kushilevitz, Eyal. Communication complexity / Eyal Kushilevitz, Noam Nisan. - Cambridge University Press, 2006. - ISBN 978-0-521-02983-4 .
Razborov A.A. Communication complexity . - ICMMO, 2012 .-- 24 p. - ISBN 978-5-4439-0202-9 .
Vereshchagin N.K., Schepin E.V. Information, coding and prediction. - M .: FMOP, ICMMO, 2012 .-- 238 p. - ISBN 978-5-94057-920-5 .

[yao1979-1] Yao, AC (1979), "Some Complexity Questions Related to Distributed Computing", Proc. of 11th STOC T. 14: 209–213

Eq	000	001	010	011	100	101	110	111
000	one	0	0	0	0	0	0	0
001	0	one	0	0	0	0	0	0
010	0	0	one	0	0	0	0	0
011	0	0	0	one	0	0	0	0
100	0	0	0	0	one	0	0	0
101	0	0	0	0	0	one	0	0
110	0	0	0	0	0	0	one	0
111	0	0	0	0	0	0	0	one

Eq	000	001	010	011	100	101	110	111
000	one	0	0	0	0	0	0	0
001	0	one	0	0	0	0	0	0
010	0	0	one	0	0	0	0	0
011	0	0	0	one	0	0	0	0
100	0	0	0	0	one	0	0	0
101	0	0	0	0	0	one	0	0
110	0	0	0	0	0	0	one	0
111	0	0	0	0	0	0	0	one