Communication Complexity

Abstract We discuss some aspects of two-party and multi-party communication complexity theory. The topics include a sample from the long list of connections of communication complexity to other models of computation which provide strong motivation to the study of this subject; separation results for restricted models such as simultaneous and one-way communication; some counter-intuitive upper bounds in these models; a new model called “communication with help, ” and a lower bound technique in this model, based on discrete Fourier analysis and multi-color discrepancy. Most of the recent results surveyed are joint work with my former and current students Anna Gál, Tom Hayes, Peter Kimmel, Satya V. Lokam.

Authors

• László Babai

Keywords

No keywords are indexed for this paper.