Communication complexity is a branch of computational complexity theory that studies the amount of communication required to solve a problem when the input is distributed among multiple parties. It specifically investigates how much information needs to be exchanged between these parties to reach a solution, given that each party has access only to part of the input. Here are some key points about communication complexity: 1. **Setting**: In a typical model, there are two parties (often referred to as Alice and Bob), each having their own input.
Articles by others on the same topic
Communication complexity studies how much information distributed parties must exchange to compute a function of their separately held inputs. Local computation is free; the resource being counted is communicated bits or qubits, with the allowed shared randomness, quantum entanglement or other correlations specified separately. For a Boolean function , a one-way exact protocol has the receiver output correctly for every input after a single message. One-bit computation using Popescu–Rohrlich boxes shows that this resource measure changes drastically if ideal superquantum boxes are available.