[talks] Omri Weinstein will present his FPO March 13, 2015 at 1pm in CS Room 301
ngotsis at CS.Princeton.EDU
Tue Mar 10 20:50:37 EDT 2015
Omri Weinstein will present his FPO on March 13, 2015 at 1pm in CS Room 301.
The members of his committee are: Mark Braverman, advisor; Anup Rao(University of Washington), reader; Zeev Dvir, reader; Sanjeev Arora, non-reader; Michael Saks(Rutgers), non-reader.
Everyone is invited to attend his talk. The talk title and abstract follow below:
Title: Interactive Information Complexity and Applications
Few models in the history of theoretical computer science have affected the field in so many ways as profoundly as communication
complexity. With applications in nearly every area of computer science, this model constitutes one of the few known techniques
for proving unconditional lower bounds - the holy grail of complexity theory. Developing tools in communication complexity is
therefore a promising approach for making progress in other computational models such as streaming, property testing, distributed
computing, circuit complexity and data structures. 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. Classical information theory, however, does not readily convert to interactive setups, where two (or more) parties must engage in a multi-round conversation in order to accomplish a desirable 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. Our main measure if interest is the Information Complexity of a function,
which informally captures the least amount of information the parties need to disclose each other about their inputs in order to solve the
We demonstrate the broad power of this theory via applications to communication complexity, data streaming, circuit lower bounds,
privacy and economics. In particular, I will discuss how information complexity helped us make progress on some of the most fundamental
questions in communication complexity, including the limits of parallel computation, interactive compression, and the KRW conjecture.
More information about the talks