CAREER: Communication, Information, and Interactive Compression

Princeton University, Princeton NJ

Investigators

Abstract

Information theory had a profound impact on both the practical and theoretical communities, finding application in almost every branch of science and beyond. Information theory is especially relevant today with the rise of the internet and data-intensive applications. Lately, many of these applications are interactive, involving several communicating parties, and the trend for more interaction is growing. Interactive information theory is a new field of study at the interface between information theory and computational complexity theory. The key ingredient that sets it apart from classical information theory is that it studies problems where parties are interacting and information flows in more than one direction. The goal of this project is to deepen our understanding of interactive information theory. Specifically, it considers the interactive compression problem, which is the interactive analogue of the data compression problem. Informally, the celebrated data compression theorems imply that every message can be compressed to its information content, measured using the Entropy function. The interactive compression problem asks whether the transcript of every communication protocol between several parties can be compressed to (roughly) its "information content." An affirmative answer to this problem would yield a powerful method for proving nearly tight communication complexity lower bounds, and may shed light on other central problems in theoretical computer science that are closely related to it, such as the direct sum and parallel repetition problems for different models, and on the log-rank conjecture. Good compression protocols also suggest a new paradigm in protocol design, where one optimizes over the information revealed by the protocol and then applies a compression scheme to obtain a protocol with low information. The study of interactive compression can also be of interest to the privacy and information theory communities, which have considered similar notions.The PI will mentor students, give tutorials and create a new course on interactive information for Computer Science and Electrical Engineering majors.