Communication Complexity and Parallel Computing

The communication complexity of two—party prools is an only 15 years old complexity measure, but it is already considered to be one of the fundamental complexity measures of recent complexity theory. Similarly to Kolmogorov complexity in the theory of sequential computations, communication complexity is used as a method for the study of the complexity of concrete computing problems in parallel information processing. Especially, it is applied to prove lower bounds that say what computer res...