Mathematics Accomplishment | 2002
Where the work was done: IBM Almaden Research Center
What we accomplished: The paper introduced a new paradigm for proving lower bounds in communication complexity using an information theoretic approach.
Communication complexity lies at the heart of computational complexity with applications to diverse areas in theoretical computer science. The immediate impact was the resolution of central open questions in data stream and sketching algorithms. Over the years, it has been tremendously influential in addressing other topics, most notably the "direct sum problem" in communication complexity. Information complexity now has its own ACM classification.
Related links: An Information Statistics Approach to Data Stream and Communication Complexity (Foundations of Computer Science, IEEE FOCS, October 2002).