
related topics 
{math, number, function} 
{system, computer, user} 
{math, energy, light} 
{government, party, election} 
{rate, high, increase} 

The notion of communication complexity (CC) was introduced by Yao in 1979^{[1]}, who investigated the following problem involving two separated parties (Alice and Bob). Alice receives an nbit string x^{[clarification needed]} and Bob another nbit string y^{[clarification needed]}, and the goal is for one of them (say Bob) to compute a certain function f(x,y)^{[clarification needed]} 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 nbit 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.
Contents
Formal definition
Let f: X Y Z where we assume in the typical case that X = Y = {0,1}^{n} and Z = {0,1}. Alice draws an nbit string x X while Bob draws an nbit string y Y. By communicating to each other one bit at a time (adopting some communication protocol), Alice and Bob want to compute the value of f(x,y) 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 D(f), is then defined to be
Full article ▸


related documents 
Semidirect product 
Riemannian manifold 
Exponential function 
Monoid 
Interpolation 
Operator 
Set (mathematics) 
Metric space 
Category theory 
P = NP problem 
Control flow 
Dirac delta function 
Busy beaver 
Imaginary unit 
Multiplication 
Finite set 
Taylor's theorem 
Uniform continuity 
Extended Euclidean algorithm 
Template (programming) 
Exponentiation by squaring 
Relational database 
VigenĂ¨re cipher 
Quadratic equation 
Hausdorff dimension 
General linear group 
Cholesky decomposition 
Icon (programming language) 
Square root 
AWK 
