Lower Bounds in Communication Complexity: A Survey

Из серии Foundations and Trends in Theoretical Computer Science издательства NOWPress, 2009, -127 pp. We survey lower bounds in communication complexity. Our focus is on lower bounds that work by first representing the communication complexity measure in Euclidean space. That is to say, the first step in these lower bound techniques is to find a geometric complexity measure such as rank, or the trace norm that serves as a lower bound to the underlying communication complexity measure. Lower bounds on this geometric complexity measure are then found using algebraic and geometric tools. Communication complexity studies how much communication is needed in order to evaluate a function whose output depends on information distributed amongst two or more parties. Yao introduced an elegant mathematical framework for the study of communication complexity, applicable in numerous situations, from an email conversation between two people, to processors communicating on a chip. Indeed, the applicability of communication complexity to other areas, including circuit and formula complexity, VLSI design, proof complexity, and streaming algorithms, is one reason why it has attracted so much study. See the excellent book of Kushilevitz and Nisan for more details on these applications and communication complexity in general. Another reason why communication complexity is a popular model for study is simply that it is an interesting mathematical model. Moreover, it has that rare combination in complexity theory of a model for which we can actually hope to show tight lower bounds, yet these bounds often require the development of nontrivial techniques and sometimes are only obtained after several years of sustained effort. Introduction Deterministic communication complexity Nondeterministic communication complexity Randomized communication complexity Quantum communication complexity The role of duality in proving lower bounds Choosing a witness Multiparty communication complexity Upper bounds on multiparty communication complexity