[talks] Omri Weinstein will present his pre-FPO Sept 16, 2014 at 11am in CS Room 401 (Title: Interactive Information Complexity and Applications)
Nicki Gotsis
ngotsis at CS.Princeton.EDU
Thu Sep 11 13:49:07 EDT 2014
Omri Weinstein will present his pre-FPO on September 16, 2014 at 11am in CS Room 401.
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
Abstract:
=======
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
underlying task.
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
mailing list