2016-T1 - Nexus of Information and Computation Theory - CEB Trimester

# playlist (click the video's upper-left icon) 

source: Institut Henri Poincaré 2016年2月1日
2016-T1 - Nexus of Information and Computation Theory - CEB Trimester
About the Program
Recently, a number of advances in the theory of computation have been made by using information-theoretic arguments. Conversely, some of the most exciting ongoing work in information theory has focused on problems with a computational component. The primary goal of this three-month IHP thematic program is to explore the rich interplay between information theory and the theory of computation, and ultimately create new connections and collaborations between both scientific communities.
The program will begin with a tutorial week at the Centre International de Recontres Mathématiques in Marseille, France. The goal is to provide sufficient background for the primary themes of the program.
The bulk of the program will be hosted at IHP in Paris, France and is organized around four primary themes, each spanning two weeks. The themes are Distributed Computation and Communication, Fundamental Inequalities and Lower Bounds, Inference Problems, and Secrecy and Privacy. Each theme is separately organized by a dedicated committee.
Finally, there will be a week-long workshop at IHP in Paris, France. The workshop will consist of talks that are aimed towards a broad audience and designed to foster discussion and interaction between the CS and IT communities.
Program Organizers
Mark Braverman (Princeton University)
Bobak Nazer (Boston University)
Anup Rao (University of Washington)
Aslan Tchamkerten, General Chair (Telecom Paristech)

Alexander Shen (LIRMM, Montpellier) 1/2 1:02:20 Different versions of Kolmogorov complexity and a priori probability: a gentle introduction 1/2
Alexander Shen (LIRMM, Montpellier)
February 01, 2016
Abstract: The informal idea – the complexity is the minimal number of bits needed to describe the object – has several different implementations. They are not only technical differences, but all they are there for a reason: we may consider binary strings (both as objects and descriptions) as self-contained objects or as partial information about infinite objects (that fixes some prefix of an infinite sequences). We will try to explain basic results about different versions of complexity and their relation to the notion of the a priori probability.
Alexander Shen (LIRMM, Montpellier) 2/2 51:36
George Giakkoupis (INRIA) 58:00
Andrei Romashchenko (LIRMM) 56:14
Yoram Moses (Technion) 1/2 58:10
Yoram Moses (Technion) 2/2 56:17
Marius Zimand (Towson University) 1:01:54
Péter Gács (Boston University) 50:40
Suresh Venkatasubramanian (University of Utah) 1/3 50:27
Suresh Venkatasubramanian (University of Utah) 2/3 43:40
Suresh Venkatasubramanian (University of Utah) 3/3 50:11
John Walsh (Drexel University) 48:46
Salim El Rouayheb (Illinois Institute of Technology) 48:43
Qin Zhang (Indiana University Bloomington) 48:45
Qi Chen (The Chinese University of Hong Kong) 52:00
Yael Kalai (Microsoft Research) 48:20
Boaz Patt-Shamir (Tel Aviv University) 45:18
Prakash Ishwar (Boston University) 58:20
Paris Koutris (University of Wisconsin) 53:23
Leonard Schulman (Caltech) 1:01:54
Klim Efremenko (Tel-Aviv University) 1/2 52:43
Klim Efremenko (Tel-Aviv University) 2/2 49:29
Yael Kalai (Microsoft Research) 55:02
Thomas Courtade (UC-Berkeley) 53:30
Ofer Feinerman (Weizmann Institute) 52:06
Anup Rao (University of Washington) 1/3 55:16
Anup Rao (University of Washington) 2/3 56:46
Anup Rao (University of Washington) 3/3 54:02
Amos Korman (CNRS/LIAFA) 42:00
Ran Gelles (Princeton University) 1/2 55:42
Ran Gelles (Princeton University) 2/2 51:37
Omri Weinstein (Courant Institute (NYU)) 2/6 55:41
Omri Weinstein (Courant Institute (NYU)) 3/6 49:36
Omri Weinstein (Courant Institute (NYU)) 4/6 1:12:42
Omri Weinstein (Courant Institute (NYU)) 5/6 56:45
Omri Weinstein (Courant Institute (NYU)) 6/6 50:56
Badih Ghazi (MIT) 55:08
Alex Sprintson (Texas A&M) 43:33
Young Han Kim (UCSD) 53:23
Michael Langberg (SUNY at Buffalo) 53:42
Allison Bishop (Columbia) 46:5
Stephan Sebastian Holzer (MIT) 50:40
János Körner (Sapienza University of Rome) 55:23
Chandra Nair (Chinese University of Hong Kong) 1/2 46:30
Chandra Nair (Chinese University of Hong Kong) 2/2 51:22
Dan Suciu (University of Washington) 51:26
Cédric Villani (Université de Lyon / Institut Henri Poincaré) 1:06:49
Péter Gács (Boston University) 2/2 51:31
Randall Dougherty (Center for Communications Research) 52:31
László Csirmaz (Central European University, Budapest) 1/3 44:10
László Csirmaz (Central European University, Budapest) 2/3 45:56
László Csirmaz (Central European University, Budapest) 3/3 38:01
Arkadev Chattopadhyay (Tata Institute of Fundamental Research) 50:09
Thathatchar.S. Jayram (IBM Almaden) 51:42
Amin Aminzadeh Gohari (Sharif University of Technology) 48:45
P. Vijay Kumar (Indian Institute of Science, University of Southern California) 42:52
František Matúš (Institute of Information Theory and Automation) 1/3 50:39
František Matúš (Institute of Information Theory and Automation) 2/3 51:47
František Matúš (Institute of Information Theory and Automation) 3/3 38:33
19 02 16 Fan Cheng (National University of Singapore) 52:44
Raymond Yeung (The Chinese University of Hong Kong) 3/3 31:34
Raymond Yeung (The Chinese University of Hong Kong) 2/3 51:01
Raymond Yeung (The Chinese University of Hong Kong) 1/3 44:59
John Walsh (Drexel University) 49:16
Sidharth Jaggi (CUHK) 38:17
Petr Kuznetsov (Télécom Paristech) 43:52
Omar Fawzi (ENS Lyon) 34:49
Ofer Shayevitz (Tel Aviv University) 34:39
Maxim Raginsky (University of Illinois) 36:50
David Woodruff (IBM Almaden) 38:48
Ankit Garg (Princeton) 35:42
Ran Gelles (Princeton) 36:54
Amir Yehudayoff (Technion) 33:16
Iordanis Kerenidis (Université Paris Diderot 7) 37:37
Ayfer Özgür (Stanford) 33:13
Rajesh Sundaresan 37:11
Sidharth Jaggi (CUHK) 34:48
Michelle Effros (California Institute of Technology) 36:15
Aaron Wagner (Cornell) 47:16
Shlomo Shamai (Technion) 38:51
Shay Moran (Technion) 24:27
Giacomo Como (Lund University) 42:28
Bruno Bauwens (Higher School of Economics) 29:06
Stephen Chestnut (ETH Zurich) 34:03
Paul Beame (University of Washington) - 1 57:40
Yuchong Hu (Huazhong University of Science and Technology) 45:26
Paul Beame (University of Washington) - 3 47:03
Paul Beame (University of Washington) - 1 47:25
David Woodruff (IBM Almaden) 52:25
Benjamin Sach (University of Bristol) 47:37
Udi Wieder (VMware Research) 49:06
Terence Chan (University of South Australia) - 3 47:29
Terence Chan (University of South Australia) - 2 47:20
Terence Chan (University of South Australia) - 1 48:34
Mokshay Madiman (University of Delaware) 47:49
Frédérique Oggier (Nanyang Technological University) 44:25
Tarik Kaced (Université de Paris-Est, LACL, UPEC) 44:05
Salman Avestimehr (USC) 49:57
Raphael Clifford (University of Bristol) - 3 39:59
Raphael Clifford (University of Bristol) - 2 50:53
Raphael Clifford (University of Bristol) - 1 40:38
Chao Tian (The University of Tennessee Knoxville) 36:27
Yitong Yin (Nanjing University) 51:36
Søren Riis (Queen Mary University of London) -2B 35:43
Søren Riis (Queen Mary University of London) 40:28
Søren Riis (Queen Mary University of London) 42:28
Babak Hassibi (Caltech) 55:06
Kasper Green Larsen (Aarhus University) - 3 38:59
Nigel Boston (University of Wisconsin) 46:18
Kasper Green Larsen (Aarhus University) - 2 35:33
Kasper Green Larsen (Aarhus University) - 1 40:56
Kenneth Shum (The Chinese University of Hong Kong) 46:01
Alex Andoni (Columbia) 1/2 47:29
Yue Lu (Harvard University) 40:14
Eric Moulines (Télécom Paristech) 56:03
Alex Andoni (Columbia) 2/2 1:02:28
Ronitt Rubinfeld (MIT and Tel Aviv University) 2/2 8:15
Ronitt Rubinfeld (MIT and Tel Aviv University) 1/2 43:00
Sudipto Guha (University of Pennsylvania) 47:05
David Woodruff (IBM Almaden) 2/2 49:51
David Woodruff (IBM Almaden) 1/2 50:07
Christian Konrad (Reykjavik University) 33:38
Michael Kapralov (EPFL) 50:53
Krzysztof Onak (IBM T. J. Watson) 42:31
Harry Lang (Johns Hopkins University) 40:56
Graham Cormode (University of Warwick) 2/2 46:40
Graham Cormode (University of Warwick) 1/2 49:14
Christian Sohler (TU Dortmund) 42:02
Arnak Dalalyan (ENSAE / CREST, GENES) 45:26
Amit Chakrabarti (Dartmouth College) 1/2 43:15
Amit Chakrabarti (Dartmouth College) 2/2 56:17
Stephen Chestnut (ETH Zurich) 46:15
Nicolas Macris (EPFL) 56:46
Pascal Vontobel (Chinese University of Hong Kong) 1:20:39
Ruediger Urbanke (EPFL) 1/2 49:26
Alexandre d'Aspremont (École Normale Supérieure) 52:44
David Gamarnik (MIT) 50:24
Ruediger Urbanke (EPFL) 2/2 38:36
Ioannis Kontoyiannis (Athens U of Econ & Business) 38:53
Mehdi Molkaraie (UPF) 41:57
Sewoong Oh (UIUC) 58:04
Galen Reeves (Duke University) 48:24
Andrew McGregor (University of Massachusetts) 2/2 39:25
Iryna Andriyanova (ETIS Lab, ENSEA/University of Cergy-Pontoise/CNRS) 51:24
Sidharth Jaggi (The Chinese University of Hong Kong) 46:52
Henry Pfister (Duke University) 1/2 54:23
Henry Pfister (Duke University) 2/2 53:21
Gábor Lugosi (Pompeu Fabra University) 2/2 39:48
Gregory Valiant (Stanford) 1/2 56:01
Ilias Diakonikolas (University of Southern California) 47:33
Gregory Valiant (Stanford) 2/2 56:17
Gábor Lugosi (Pompeu Fabra University) 1/2 46:18
Andrew McGregor (University of Massachusetts) 1/2 1:02:39
Ilias Diakonikolas (University of Southern California) 47:33
Gregory Valiant (Stanford) 2/2 56:17
Gregory Valiant (Stanford) 1/2 56:01
Gábor Lugosi (Pompeu Fabra University) 2/2 39:48
Gábor Lugosi (Pompeu Fabra University) 1/2 46:18
Negar Kiyavash (UIUC) 1:03:01
Sennur Ulukus (University of Maryland) 58:11
Stephanie Wehner (Delft University of Technology) 56:17
Krzysztof Pietrzak (IST Austria) 58:57
Andreas Winter (Universitat Autonoma de Barcelona) 51:31
Yingbin Liang (Syracuse University) 49:39
Sirin Nitinawarat (Qualcomm Technologies, Inc.) 26:49
Matthieu Bloch (Georgia Tech) 55:53
Alex Vardy (University of California, San Diego) 54:34
Stefano Tessaro (University of California, Santa Barbara) 54:49
Stefan Dziembowski (University of Warsaw) 48:26
Imre Csiszár (Renyi Institute, Budapest) 58:46
Shun Watanabe (Tokyo University of Agriculture and Technology) 3/3 57:35
H. Tyagi - S. Watanabe 2/3 52:12
Himanshu Tyagi (Indian Institute of Science, Bangalore) 1/3 52:53
Yevgeniy Dodis (NYU) 59:20
Luca Trevisan (University of California, Berkeley) 50:48
Iftach Haitner (Tel Aviv University) - Leo Reyzin (Boston University) 3/3 54:24
Iftach Haitner (Tel Aviv University) - Leo Reyzin (Boston University) 2/3 48:19
Iftach Haitner (Tel Aviv University) - Leo Reyzin (Boston University) 1/3 50:02
Daniel Wichs (Northeastern) 56:56
Huijia Lin (University of California, Santa Barbara) 57:00
Yuval Ishai (Technion) 1/2 50:19
Yuval Ishai (Technion) - 2/2 31:49
Manoj Prabhakaran (University of Illinois) - 1/2 22:14
Manoj Prabhakaran (University of Illinois) - 2/2 52:15
Hoeteck Wee (ENS, Paris) 52:09
Manoj Prabhakaran (University of Illinois at Urbana-Champaign) 58:12
Ye Wang (Mitsubishi Electric Research Laboratories) 47:00
Adam Smith (Penn State) - 1/3 59:30
Adam Smith (Penn State) - 2/3 56:54
Cynthia Dwork (Microsoft Research) 50:38
Adam Smith (Penn State) - 3/3 51:23
Joerg Kliewer (New Jersey Institute of Technology) 57:02
Sewoong Oh (University of Illinois) 49:13
Moni Naor (Wezimann Institute of Science) 46:12
Kobbi Nissim (CRCS at Harvard and Ben-Gurion University) 53:08
Delaram Kahrobaei (City University of New York) 46:33
Lalitha Sankar (Arizona State University) 1:00:41
Jonathan Ullman (Northeastern University) 51:57
Kamalika Chaudhuri (UC San Diego) 52:26
Arkadev Chattopadhyay (TIFR) 57:06