Information Complexity       


Mathematics Accomplishment | 2002

IBM researchers:

Where the work was doneIBM Almaden Research Center

What we accomplishedThe 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).

 

BACK TO MATHEMATICS

BACK TO IBM RESEARCH ACCOMPLISHMENTS