Credit points: 2.0
Communication complexity deals with measuring the amount of communication needed for computing functions and relations whose inputs are distributed among two or more processors. The course presents upper and lower bounds in several models: deterministic,nondeterministic and probabilistic. The results are proven using combinatorial, probabilistic and algebraic methods. Applications of the results to complexity theory and VLSI will be presented.