Lesson plan
Communication complexity
In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first introduced by Andrew Yao in 1979, while studying the problem of computation distributed among several machines. The problem is usually stated as follows: two parties (traditionally called Alice and Bob) each receive a (potentially different) n -bit string x and y . The goal is for Alice to compute the value of a certain function, f(x, y) , that depends on both x and y , with the least amount of communication between them. While Alice and Bob can always succeed by having Bob send his whole n -bit string to Alice (who then computes the function f ), the idea here is to find clever ways of calculating f with fewer than n bits of communication. Note that, unlike in computational complexity theory, communication complexity is not concerned with the amount of computation performed by Alice or Bob, or the size of the memory used, as we generally assume nothing about the computational power of either Alice or Bob. This abstract problem with two parties (called two-party communication complexity), and its general form with more than two parties, is relevant in many contexts.…
Article summary
In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first introduced by Andrew Yao in 1979, while studying the problem of computation distributed among several machines. The problem is usually stated as follows: two parties (traditionally called Alice and Bob) each receive a (potentially different) n -bit string x and y . The goal is for Alice to compute the value of a certain function, f(x, y) , that depends on both x and y , with the least amount of communication between them. While Alice and Bob can always succeed by having Bob send his whole n -bit string to Alice (who then computes the function f ), the idea here is to find clever ways of calculating f with fewer than n bits of communication. Note that, unlike in computational complexity theory, communication complexity is not concerned with the amount of computation performed by Alice or Bob, or the size of the memory used, as we generally assume nothing about the computational power of either Alice or Bob. This abstract problem with two parties (called two-party communication complexity), and its general form with more than two parties, is relevant in many contexts.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.