Communication complexity

ID: communication-complexity

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.

New to topics? Read the docs here!