Amit Chakrabarti's work receives Test-of-Time Award

In 2001, Professor Amit Chakrabarti and his collaborators developed a new way of analyzing communication protocols using information theory, which birthed the concept of "information complexity". This work, published at the IEEE FOCS 2001 conference, is now being recognized by FOCS 2021 with a 20-year Test-of-Time Award. 

A communication protocol is an algorithm collaboratively executed by two or more "players" to jointly solve a computational problem whose inputs are distributed among those players. Executing such a protocol causes some number of bits to be communicated among the players and minimizing this number is a key objective. Understanding the minimum possible communication necessary to solve a particular problem (called its communication complexity) is a key step in obtaining results in a broad range of areas, including data structures, data streams, Boolean circuits, logic, quantum computing, game theory and optimization. The method introduced by Professor Chakrabarti and his collaborators gives a new recipe for proving theorems about communication complexity. Roughly speaking, it transforms the challenge of understanding communication complexity from a combinatorial problem to an information-theoretic one, which then makes the rich body of analytical methods from information theory applicable. Information complexity has been grown and extended by numerous research groups all over the world and today it is a subfield of research in its own right.

The IEEE Symposium on Foundations of Computer Science (FOCS) is the flagship conference sponsored by the IEEE Computer Society and covers a broad range of theoretical computer science.