אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Over the past three decades, communication complexity has found applications in nearly every area of computer science, and constitutes one of the few known techniques for proving unconditional lower bounds.

Developing tools in communication complexity is thus a promising approach for making progress in other computational models such as circuit complexity, streaming, data structures and privacy to mention a few.

One striking example of such tool is information theory, introduced by Shannon in the late 1940's in the context of the one way data transmission problem. Shannon's work revealed the intimate connection between information and communication, namely, that the amortized transmission cost of a random message is equal to the amount of information it contains. This compression theory, however, does not readily convert to interactive setups, where two (or more) parties must engage in a multi-round conversation to accomplish a task.

The goal of our ongoing research is to extend this theory, develop the right tools, and understand how information behaves in interactive setups, such as the communication complexity model.

In this introductory talk, I will give an overview of Information Complexity, an interactive analogue of Shannon's theory. I will describe some of the main open problems in this emerging field, and some of the interesting applications we found, including an exact bound on the communication complexity of the Set Disjointness function (~0.48n), and how information helped us understand the limits of parallel computation.