Interactive Information Complexity and Applications: Interactive Compression - Part 2-1
703 views · Published 25 February 2016 · 56:45 · Indexed 20 September 2026
Channel: Institut Henri Poincaré · 2016 · Science & Technology
By Omri Weinstein (Courant Institute (NYU)) Abstract: Communication complexity had a profound impact on nearly every field of theoretical computer science, and is one of the rare methods for proving unconditional lower bounds. Developing new tools in communication complexity is therefore vital for making progress in other computational models, such as circuit complexity, streaming algorithms, property testing, data structures and VLSI chip design. In this 3-hour mini-course, I will give an introduction to Information Complexity, an interactive analogue of Shannon's information theory, which has recently found many applications in theoretical computer science and in particular for understanding the limitations of parallel computing. Such applications give rise to the fascinating problem of compressing interactive protocols, which will be at the core of this seminar. I will survey some of the exciting recent progress in the field, and some applications of information complexity to parallel computing and secure computation. No prior knowledge will be assumed in this talk.
More from this channel
-
54:09
Le nombre de rotation et ses avatars
-
32:09
Hénon's generating solutions and the structure of periodic orbits families...
-
38:22
Michel Hénon et les amas globulaires
-
20:25
1 - Kick-off afternoon : introduction and welcoming word by Cédric Villani
-
1:35:37
Topological Recursion - 2/8
-
4:07
Présentation du trimestre Stochastic Dynamics Out of Equilibrium à l'IHP
-
1:29:17
Stochastic Resetting - Lecture 1
-
51:01
Ramsey theorems for classes of structures with functions and relations