Programs
Spring 2015

Information Theory

Jan. 13May 15, 2015

Communication and computation are intrinsically intertwined. To compute, one must often communicate. To communicate reliably, one needs to compute. It is no wonder that information theory, invented by Claude Shannon in 1948 as the mathematical underpinning of communication engineering, has had many ties with the theory of computing. From an engineering point of view, information theory focuses on how much information an engineered system can extract and provides a complementary viewpoint to the theory of computing, which focuses on how efficiently such information can be extracted.

Traditionally, much of the research in this area has been done by two separate communities, one in electrical engineering and one in theoretical computer science.  The purpose of the program is to strengten the intellectual ties between these two communities and to exploit their complementary viewpoints to solve engineering and fundamental mathematical problems of current interest. In particular, the program will explore three main themes: (1) information theoretic techniques in complexity theory and combinatorics, focusing particularly on areas where there have been significant recent advances, such as information theoretic lower bounds in communication complexity and streaming; (2) coding theory and applications, focusing on new requirements driven by modern applications, as well as cross-fertilization of concepts recently developed in one of the two communities (e.g., polar codes, spatial coupling, sub-linear decoding, computationally bounded channels); (3) information theory, machine learning, and big data, focusing on the problem of learning high dimensional structures from multiple points of view: high-dimensional statistics, large-alphabet compression, compressed sensing and sublinear sampling.

The program will benefit from significant participation from the Center for Science of Information (an NSF Science and Technology Center), including sponsorship of the workshop on Information Theory, Learning and Big Data.

sympa [at] lists [dot] simons [dot] berkeley [dot] edu (body: subscribe%20it2015announcements%40lists.simons.berkeley.edu) (Click here to subscribe to our announcements email list for this program.)

Organizers: 
Venkat Guruswami (Carnegie Mellon University; co-chair), David Tse (Stanford University; co-chair), Michael Luby (Qualcomm Inc), Alon Orlitsky (UC San Diego), Jaikumar Radhakrishnan (Tata Institute of Fundamental Research).
Long-Term Participants (including Organizers): 
Emmanuel Abbe (Princeton University), Venkat Anantharam (UC Berkeley), Elaine Angelino (UC Berkeley), Alexandr Andoni (Microsoft Research), Erdal Arikan (Bilkent University), Peter Bartlett (UC Berkeley), Amit Chakrabarti (Dartmouth College), Arkadev Chattopadhyay (Tata Institute of Fundamental Research), Thomas Courtade (UC Berkeley), Marco Dalai (Brescia University), Suhas Diggavi (UCLA), Vitaly Feldman (IBM Research), Anna Gál (University of Texas, Austin), Parikshit Gopalan (Microsoft Research), Venkat Guruswami (Carnegie Mellon University; co-chair), Thomas Holenstein (ETZ Zürich), Rahul Jain (National University of Singapore), T.S. Jayram (IBM Almaden), Navin Kashyap (Indian Institute of Science), Cari Kaufman (UC Berkeley), Lap-Chi Lau (The Chinese University of Hong Kong), Nati Linial (Hebrew University of Jerusalem), Michael Luby (Qualcomm Inc), Raghu Meka (Microsoft Research), Olgica Milenkovic (University of Illinois, Urbana-Champaign), Gary Miller (Carnegie Mellon University), Andrea Montanari (Stanford University), Elchanan Mossel (UC Berkeley), Chandra Nair (The Chinese University of Hong Kong), Alon Orlitsky (UC San Diego), Henry Pfister (Texas A&M University), Toniann Pitassi (University of Toronto), Jaikumar Radhakrishnan (Tata Institute of Fundamental Research), Kannan Ramchandran (UC Berkeley), Anup Rao (University of Washington), Ran Raz (Weizmann Institute), Thomas Richardson (Qualcomm Inc), Atri Ruda (University of Buffalo), Anant Sahai (UC Berkeley), Narayana Santhanam (University of Hawaii), Leonard Schulman (California Institute of Technology), Emina Soljanin (Bell Labs), David Tse (Stanford University; co-chair), Rüdiger Urbanke (Ecole Polytechnique Fédérale de Lausanne), Sergio Verdú (Princeton University), Martin Wainwright (UC Berkeley), Mary Wootters (Carnegie Mellon University), Sergey Yekhanin (Microsoft Research), Bin Yu (UC Berkeley).
Research Fellows: 
Mahdi Cheraghchi (Massachusetts Institute of Technology; Qualcomm Research Fellow), Klim Efremenko (Tel Aviv University), Victoria Kostina (Princeton University), Shannon McCurdy (UC Berkeley), Huy Nguyen (Princeton University; Google Research Fellow), Samet Oymak (California Institute of Technology), Yury Polyanskiy (Massachusetts Institute of Technology), Benjamin Rossman (National Institute of Informatics, Tokyo), Eren Şaşoğlu (UC Berkeley), Ilan Shomorony (Cornell University), Li-Yang Tan (Columbia University; Microsoft Research Fellow), Yihong Wu (University of Illinois, Urbana-Champaign).
Visiting Graduate Students: 
Ankit Garg (Princeton University), Ameya Velingker (Carnegie Mellon University), Carol Wang (Carnegie Mellon University), Omri Weinstein (Princeton University).

Workshops

Jan. 13Jan. 16, 2015
Organizers: Venkat Guruswami (Carnegie Mellon University), David Tse (Stanford University)
Feb. 9Feb. 13, 2015
Organizers: Michael Luby (Qualcomm Inc; chair), Alex Dimakis (University of Texas, Austin), Thomas Richardson (Qualcomm Inc), Rüdiger Urbanke (Ecole Polytechnique Fédérale de Lausanne)
Mar. 16Mar. 20, 2015
Organizers: Alon Orlitsky (UC San Diego; co-chair), David Tse (Stanford University; co-chair), Narayana Santhanam (University of Hawaii), Tsachy Weissman (Stanford University)
Apr. 20Apr. 24, 2015
Organizers: Jaikumar Radhakrishnan (Tata Institute of Fundamental Research; chair), Mark Braverman (Princeton University), Venkat Guruswami (Carnegie Mellon University), Ran Raz (Weizmann Institute)

Those interested in participating in this program should inftheory [at] lists [dot] simons [dot] berkeley [dot] edu (send an email to the organizers)

Progam image: "When Shannon met Turing" by Rodrigo Barreto.