Communication complexity
Encyclopedia
The notion of communication complexity was introduced by Yao
in 1979,
who investigated the following problem involving two separated parties (Alice and Bob
). Alice receives an n-bit
string x and Bob another n-bit string y, and the goal is for one of them (say Bob) to compute a certain function f(x,y) with the least amount of communication between them. Note that here we are not concerned about the number of computational steps, or the size of the computer memory
used. Communication complexity tries to quantify the amount of communication required for such distributed computations.
Of course they can always succeed by having Alice send her whole n-bit string to Bob, who then computes the function, but the idea here is to find clever ways of calculating f with less than n bits of communication.
This abstract problem is relevant in many contexts: in VLSI circuit design, for example, one wants to minimize energy used by decreasing the amount of electric signals required between the different components during a distributed computation. The problem is also relevant in the study of data structures, and in the optimization of computer networks. For a survey of the field, see the book by Kushilevitz and Nisan.
: X 
Y 
Z where we assume in the typical case that 
and 
. Alice draws an n-bit string 
X while Bob draws an n-bit string 
Y. By communicating to each other one bit
at a time (adopting some communication protocol), Alice and Bob want to compute the value of
such that at least one party knows the value at the end of the communication. It is trivial to see that once one party knows the answer, with one more bit exchange, both parties know the answer. The worst case communication complexity of this communication protocol, denoted as 
, is then defined to be
minimum number of bits exchanged between Alice and Bob in the worst case
Using the above definition, it is useful to think of the function
as a matrix
(called the input matrix) where each row of the matrix corresponds to 
X and each column corresponds to 
Y. An entry in the input matrix is 
. Initially both Alice and Bob have a copy of the entire matrix A (assuming the function 
is known to both). Then, the problem of computing the function value can be rephrased as "zeroing-in" on the corresponding matrix entry. This problem can be solved if either Alice or Bob knows both 
and 
. At the start of communication, the number of choices for the value of the function on the inputs is the size of matrix, i.e. 
. Then, as and when each party communicates a bit to the other, the number of choices for the answer reduces as this eliminates a set of rows/columns resulting in a submatrix of A.
More formally, a set R
X 
Y is called a (combinatorial) rectangle if whenever 
R and 
R then 
R. Equivalently, R can also be viewed as a submatrix of the input matrix A such that R = M 
N where M 
X and N 
Y. Consider the case when 
bits are already exchanged between the parties. Now, for a particular 
, let us define a matrix
the k-bits exchanged on input 
is 
}
Then,
X 
Y, and 
is a rectangle and a submatrix of A.
is equal to 
. It is easy to prove that the equality problem (EQ) will always require you to communicate 
bits in the worst case if you want to be absolutely sure 
and 
are equal.
Consider the simple case of
and 
being 3 bits. The equality function in this case can be represented by the matrix below. The rows representing all the possibilities of 
, the columns those of 
.
As you can see, the function only evaluates to 1 when
equals 
(i.e., on the diagonal). It is also fairly easy to see how communicating a single bit divides your possibilities in half. If you know that the first bit of 
is 1, you only need to consider half of the columns (where 
can equal 100, 101, 110, or 111).
Theorem:
.
Proof. Assume that
. This means that there exists an 
and an 
having the same history, 
. Since this history defines a rectangle, 
must also be 1. By definition 
and we know that equality is only true for 
when 
. Thus, we have a contradiction.
Intuitively, for
less than 
, we need to be able to define a rectangle in the EQ matrix greater in size than a single cell. All of the cells in this rectangle must contain 1 for us to be able to generalize that this rectangle equals 1. It is not possible to form such a rectangle in the equality matrix.
with much less information exchanged? Yao, in his seminal paper
answers this question by defining randomized communication complexity.
A randomized protocol
for a function 
has two-sided error.
A randomized protocol is a deterministic protocol that uses an extra random string in addition to its normal input. There are two models for this: a public string is a random string that is known by both parties beforehand, while a private string is generated by one party and must be communicated to the other party. A theorem presented below shows that any public string protocol can be simulated by a private string protocol that uses O(log n) additional bits compared to the original.
Note that in the probability inequalities above, the outcome of the protocol is understood to depend only on the random string; both strings x and y remain fixed. In other words, if R(x,y) yields g(x,y,r) when using random string r, then g(x,y,r) = f(x,y) for at least half of all choices for the string r.
The randomized complexity is simply defined as the number of bits exchanged in such a protocol.
Note that it is also possible to define a randomized protocol with one-sided error, and the complexity is defined similarly.
. Alice computes 
and sends this bit (call it b) to Bob. (The 
is the dot product
in GF(2).) Then Bob compares b to
. If they are the same, then Bob accepts, saying x equals y. Otherwise, he rejects.
Clearly, if
, then 
, so 
. If x does not equal y, it is still possible that 
, which would give Bob the wrong answer. How does this happen?
If x and y are not equal, they must differ in some locations:
Where
and 
agree, 
so those terms affect the dot products equally. We can safely ignore those terms and look only at where 
and 
differ. Furthermore, we can swap the bits 
and 
without changing whether or not the dot products are equal. This means we can swap bits so that 
contains only zeros and 
contains only ones:
Note that
and 
. Now, the question becomes: for some random string 
, what is the probability that 
? Since each 
is equally likely to be 
or 
, this probability is just 
. Thus, when 
does not equal 
,
. The algorithm can be repeated many times to increase its accuracy. This fits the requirements for a randomized communication algorithm.
This shows that if Alice and Bob share a random string of length n, they can send one bit to each other to compute
. In the next section, it is shown that Alice and Bob can exchange only O(log n) bits that are as good as sharing a random string of length n. Once that is shown, it follows that EQ can be computed in O(log n) messages.
-bit string can be simulated by a private string protocol that uses an extra O(log n) bits.
Intuitively, we can find some set of strings that has enough randomness in it to run the random protocol with only a small increase in error. This set can be shared beforehand, and instead of drawing a random string, Alice and Bob need only agree on which string to choose from the shared set. This set is small enough that the choice can be communicated efficiently. A formal proof follows.
Consider some random protocol P with a maximum error rate of 0.1. Let
be 
strings of length n, numbered 
. Given such an 
, define a new protocol 
which randomly picks some 
and then runs P using 
as the shared random string. It takes O(log 100n) = O(log n) bits to communicate the choice of 
.
Let us define
and 
to be the probabilities that 
and 
compute the correct value for the input 
.
For a fixed
, we can use Hoeffding's inequality
to get the following equation:
Thus when we don't have
fixed:
The last equality above holds because there are
different pairs 
. Since the probability does not equal 1, there is some 
so that for all 
:
Since
has at most 0.1 error probability, 
can have at most 0.2 error probability.
At least three quantum generalizations of communication complexity have been proposed; for a survey see the suggested text by G. Brassard.
The first one is the qubit-communication model
, where the parties can use quantum communication instead of classical communication, for example by exchanging photons through an optical fiber
.
In a second model the communication is still performed with classical bits, but the parties are allowed to manipulate an unlimited supply of quantum entangled states as part of their protocols. By doing measurements on their entangled states, the parties can save on classical communication during a distributed computation.
The third model involves access to previously shared entanglement in addition to qubit
communication, and is the least explored of the three quantum models.
Viewed differently, this amounts to covering all 1-entries of the 0/1-matrix by combinatorial 1-rectangles (i.e., non-contiguous, non-convex submatrices, whose entries are all one (see Kushilevitz and Nisan or Dietzfelbinger et al.)). The nondeterministic communication complexity is the binary logarithm of the rectangle covering number of the matrix: the minimum number of combinatorial 1-rectangles required to cover all 1-entries of the matrix, without covering any 0-entries.
Nondeterministic communication complexity occurs as a means to obtaining lower bounds for deterministic communication complexity (see Dietzfelbinger et al.), but also in the theory of nonnegative matrices, where it gives a lower bound on the nonnegative rank
of a nonnegative matrix.
, the minimum number of bits exchanged to compute 
deterministically in the worst case, 
, is known to be bounded from below by the logarithm of the rank
of the matrix
. The log rank conjecture proposes that the communication complexity, 
, of 
is bounded from above by a constant power of the logarithm of the rank of 
. Since D(f) is bounded from above and below by polynomials of log rank
, we can say D(f) is polynomially related to log rank
. Since the rank of a matrix is polynomial time computable in the size of the matrix, such an upper bound would allow the matrix's communication complexity to be approximated in polynomial time. Note, however, that the size of the matrix itself is exponential in the size of the input.
For a randomized protocol, the number of bits exchanged in the worst case, R(f), is conjectured to be polynomially related to the following formula:
Such log rank conjectures are valuable because they reduce the question of a matrix's communication complexity to a question of linearly independent rows (columns) of the matrix. This reveals that the essence of the communication complexity problem, for example in the EQ case above, is figuring out where in the matrix the inputs are, in order to find out if they're equivalent.
Andrew Yao
Andrew Chi-Chih Yao is a prominent computer scientist and computational theorist. Yao used the minimax theorem to prove what is now known as Yao's Principle.Yao was born in Shanghai, China...
in 1979,
who investigated the following problem involving two separated parties (Alice and Bob
Alice and Bob
The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...
). Alice receives an n-bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
string x and Bob another n-bit string y, and the goal is for one of them (say Bob) to compute a certain function f(x,y) with the least amount of communication between them. Note that here we are not concerned about the number of computational steps, or the size of the computer memory
Computer memory
In computing, memory refers to the physical devices used to store programs or data on a temporary or permanent basis for use in a computer or other digital electronic device. The term primary memory is used for the information in physical systems which are fast In computing, memory refers to the...
used. Communication complexity tries to quantify the amount of communication required for such distributed computations.
Of course they can always succeed by having Alice send her whole n-bit string to Bob, who then computes the function, but the idea here is to find clever ways of calculating f with less than n bits of communication.
This abstract problem is relevant in many contexts: in VLSI circuit design, for example, one wants to minimize energy used by decreasing the amount of electric signals required between the different components during a distributed computation. The problem is also relevant in the study of data structures, and in the optimization of computer networks. For a survey of the field, see the book by Kushilevitz and Nisan.
Formal definition
Let: X Y Z where we assume in the typical case that and . Alice draws an n-bit string X while Bob draws an n-bit string Y. By communicating to each other one bitBit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
at a time (adopting some communication protocol), Alice and Bob want to compute the value of
such that at least one party knows the value at the end of the communication. It is trivial to see that once one party knows the answer, with one more bit exchange, both parties know the answer. The worst case communication complexity of this communication protocol, denoted as , is then defined to be minimum number of bits exchanged between Alice and Bob in the worst caseUsing the above definition, it is useful to think of the function
as a matrixMatrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
(called the input matrix) where each row of the matrix corresponds to X and each column corresponds to Y. An entry in the input matrix is . Initially both Alice and Bob have a copy of the entire matrix A (assuming the function is known to both). Then, the problem of computing the function value can be rephrased as "zeroing-in" on the corresponding matrix entry. This problem can be solved if either Alice or Bob knows both and . At the start of communication, the number of choices for the value of the function on the inputs is the size of matrix, i.e. . Then, as and when each party communicates a bit to the other, the number of choices for the answer reduces as this eliminates a set of rows/columns resulting in a submatrix of A.More formally, a set R
X Y is called a (combinatorial) rectangle if whenever R and R then R. Equivalently, R can also be viewed as a submatrix of the input matrix A such that R = M N where M X and N Y. Consider the case when bits are already exchanged between the parties. Now, for a particular , let us define a matrix the k-bits exchanged on input is }Then,
X Y, and is a rectangle and a submatrix of A.Example: EQ
We consider the case where Alice and Bob try to determine if they both have the same string. That is, we are trying to determine if is equal to . It is easy to prove that the equality problem (EQ) will always require you to communicate bits in the worst case if you want to be absolutely sure and are equal.Consider the simple case of
and being 3 bits. The equality function in this case can be represented by the matrix below. The rows representing all the possibilities of , the columns those of .| EQ | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
| 000 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 001 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 010 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 011 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 100 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 101 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 110 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 111 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
As you can see, the function only evaluates to 1 when
equals (i.e., on the diagonal). It is also fairly easy to see how communicating a single bit divides your possibilities in half. If you know that the first bit of is 1, you only need to consider half of the columns (where can equal 100, 101, 110, or 111).Theorem:
.Proof. Assume that
. This means that there exists an and an having the same history, . Since this history defines a rectangle, must also be 1. By definition and we know that equality is only true for when . Thus, we have a contradiction.Intuitively, for
less than , we need to be able to define a rectangle in the EQ matrix greater in size than a single cell. All of the cells in this rectangle must contain 1 for us to be able to generalize that this rectangle equals 1. It is not possible to form such a rectangle in the equality matrix.Randomized communication complexity
In the above definition, we are concerned with the number of bits that must be deterministically transmitted between two parties. If both the parties are given access to a random number generator, can they determine the value of with much less information exchanged? Yao, in his seminal paperanswers this question by defining randomized communication complexity.
A randomized protocol
for a function has two-sided error.A randomized protocol is a deterministic protocol that uses an extra random string in addition to its normal input. There are two models for this: a public string is a random string that is known by both parties beforehand, while a private string is generated by one party and must be communicated to the other party. A theorem presented below shows that any public string protocol can be simulated by a private string protocol that uses O(log n) additional bits compared to the original.
Note that in the probability inequalities above, the outcome of the protocol is understood to depend only on the random string; both strings x and y remain fixed. In other words, if R(x,y) yields g(x,y,r) when using random string r, then g(x,y,r) = f(x,y) for at least half of all choices for the string r.
The randomized complexity is simply defined as the number of bits exchanged in such a protocol.
Note that it is also possible to define a randomized protocol with one-sided error, and the complexity is defined similarly.
Example: EQ
Returning to the previous example of EQ, if certainty is not required, Alice and Bob can check for equality using only O(log n) messages. Consider the following protocol: Assume that Alice and Bob both have access to the same random string. Alice computes and sends this bit (call it b) to Bob. (The is the dot productDot product
In mathematics, the dot product or scalar product is an algebraic operation that takes two equal-length sequences of numbers and returns a single number obtained by multiplying corresponding entries and then summing those products...
in GF(2).) Then Bob compares b to
. If they are the same, then Bob accepts, saying x equals y. Otherwise, he rejects.Clearly, if
, then , so . If x does not equal y, it is still possible that , which would give Bob the wrong answer. How does this happen?If x and y are not equal, they must differ in some locations:
Where
and agree, so those terms affect the dot products equally. We can safely ignore those terms and look only at where and differ. Furthermore, we can swap the bits and without changing whether or not the dot products are equal. This means we can swap bits so that contains only zeros and contains only ones:Note that
and . Now, the question becomes: for some random string , what is the probability that ? Since each is equally likely to be or , this probability is just . Thus, when does not equal ,. The algorithm can be repeated many times to increase its accuracy. This fits the requirements for a randomized communication algorithm.This shows that if Alice and Bob share a random string of length n, they can send one bit to each other to compute
. In the next section, it is shown that Alice and Bob can exchange only O(log n) bits that are as good as sharing a random string of length n. Once that is shown, it follows that EQ can be computed in O(log n) messages.Public coins versus private coins
It is easier to create random protocols when both parties have access to the same random string (shared string protocol). It is still possible to use these protocols even when the two parties don't share a random string (private string protocol) with a small communication cost. Any shared string random protocol using an-bit string can be simulated by a private string protocol that uses an extra O(log n) bits.Intuitively, we can find some set of strings that has enough randomness in it to run the random protocol with only a small increase in error. This set can be shared beforehand, and instead of drawing a random string, Alice and Bob need only agree on which string to choose from the shared set. This set is small enough that the choice can be communicated efficiently. A formal proof follows.
Consider some random protocol P with a maximum error rate of 0.1. Let
be strings of length n, numbered . Given such an , define a new protocol which randomly picks some and then runs P using as the shared random string. It takes O(log 100n) = O(log n) bits to communicate the choice of .Let us define
and to be the probabilities that and compute the correct value for the input .For a fixed
, we can use Hoeffding's inequalityHoeffding's inequality
In probability theory, Hoeffding's inequality provides an upper bound on the probability for the sum of random variables to deviate from its expected value. Hoeffding's inequality was proved by Wassily Hoeffding.LetX_1, \dots, X_n \!...
to get the following equation:
Thus when we don't have
fixed:The last equality above holds because there are
different pairs . Since the probability does not equal 1, there is some so that for all :Since
has at most 0.1 error probability, can have at most 0.2 error probability.Quantum communication complexity
Quantum communication complexity tries to quantify the communication reduction possible by using quantum effects during a distributed computation.At least three quantum generalizations of communication complexity have been proposed; for a survey see the suggested text by G. Brassard.
The first one is the qubit-communication model
Quantum entanglement
Quantum entanglement occurs when electrons, molecules even as large as "buckyballs", photons, etc., interact physically and then become separated; the type of interaction is such that each resulting member of a pair is properly described by the same quantum mechanical description , which is...
, where the parties can use quantum communication instead of classical communication, for example by exchanging photons through an optical fiber
Optical fiber
An optical fiber is a flexible, transparent fiber made of a pure glass not much wider than a human hair. It functions as a waveguide, or "light pipe", to transmit light between the two ends of the fiber. The field of applied science and engineering concerned with the design and application of...
.
In a second model the communication is still performed with classical bits, but the parties are allowed to manipulate an unlimited supply of quantum entangled states as part of their protocols. By doing measurements on their entangled states, the parties can save on classical communication during a distributed computation.
The third model involves access to previously shared entanglement in addition to qubit
Qubit
In quantum computing, a qubit or quantum bit is a unit of quantum information—the quantum analogue of the classical bit—with additional dimensions associated to the quantum properties of a physical atom....
communication, and is the least explored of the three quantum models.
Nondeterministic communication complexity
In nondeterministic communication complexity, Alice and Bob have access to an oracle. After receiving the oracle's word, the parties communicate to deduce f(x,y). The nondeterministic communication complexity is then the maximum over all pairs (x,y) over the sum of number of bits exchanged and the coding length of the oracle word.Viewed differently, this amounts to covering all 1-entries of the 0/1-matrix by combinatorial 1-rectangles (i.e., non-contiguous, non-convex submatrices, whose entries are all one (see Kushilevitz and Nisan or Dietzfelbinger et al.)). The nondeterministic communication complexity is the binary logarithm of the rectangle covering number of the matrix: the minimum number of combinatorial 1-rectangles required to cover all 1-entries of the matrix, without covering any 0-entries.
Nondeterministic communication complexity occurs as a means to obtaining lower bounds for deterministic communication complexity (see Dietzfelbinger et al.), but also in the theory of nonnegative matrices, where it gives a lower bound on the nonnegative rank
Nonnegative rank (linear algebra)
In linear algebra, the nonnegative rank of a nonnegative matrix is a concept similar to the usual linear rank of a real matrix, but adding the requirement that certain coefficients and entries of vectors/matrices have to be nonnegative....
of a nonnegative matrix.
Open problems
Considering a 0/1 input matrix, the minimum number of bits exchanged to compute deterministically in the worst case, , is known to be bounded from below by the logarithm of the rankRank (linear algebra)
The column rank of a matrix A is the maximum number of linearly independent column vectors of A. The row rank of a matrix A is the maximum number of linearly independent row vectors of A...
of the matrix
. The log rank conjecture proposes that the communication complexity, , of is bounded from above by a constant power of the logarithm of the rank of . Since D(f) is bounded from above and below by polynomials of log rank, we can say D(f) is polynomially related to log rank. Since the rank of a matrix is polynomial time computable in the size of the matrix, such an upper bound would allow the matrix's communication complexity to be approximated in polynomial time. Note, however, that the size of the matrix itself is exponential in the size of the input.For a randomized protocol, the number of bits exchanged in the worst case, R(f), is conjectured to be polynomially related to the following formula:
Such log rank conjectures are valuable because they reduce the question of a matrix's communication complexity to a question of linearly independent rows (columns) of the matrix. This reveals that the essence of the communication complexity problem, for example in the EQ case above, is figuring out where in the matrix the inputs are, in order to find out if they're equivalent.