This project explores fundamental questions in communication complexity, data structures and circuit complexity. Despite much effort, only a few methods have been developed for proving lower bounds on the efficiency of computational models. In this project, the PI will study a family of techniques applicable to understanding lower bounds in communication complexity, data structures, and boolean circuit complexity. The PI will study both longstanding open problems regarding these computational models, and topics that have not yet been widely considered.
A common theme is the use of methods from information theory to measure how the information flows in the computational systems of interest. Methods from information theory have been used to great advantage in this arena recently, and this project seeks to further explore how analyzing the flow of information can help understand the limits of computational processes. The PI plans to organize a workshop on information theory methods in computer science.
