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 strengthen 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.



Venkat Guruswami (Carnegie Mellon University; co-chair), David Tse (Stanford University; co-chair), Mike 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), Alexandr Andoni (Columbia University), Elaine Angelino (UC Berkeley), Erdal Arıkan (Bilkent University), Peter Bartlett (UC Berkeley), Guy Bresler (Massachusetts Institute of Technology), Amit Chakrabarti (Dartmouth College), Arkadev Chattopadhyay (Tata Institute of Fundamental Research), Thomas Courtade (UC Berkeley), Marco Dalai (Brescia University), Suhas Diggavi (UCLA), Cynthia Dwork (Microsoft Research), Alina Ene (Warwick University), Vitaly Feldman (IBM Research), Alyson Fletcher (UC Santa Cruz), Anna Gál (University of Texas, Austin), Parikshit Gopalan (Microsoft), Venkat Guruswami (Carnegie Mellon University; co-chair), Prahladh Harsha (Tata Institute of Fundamental Research), Thomas Holenstein (ETH Zürich), Rahul Jain (National University of Singapore), Adel Javanmard (Stanford University), T.S. Jayram (IBM Almaden), Ravi Kannan (Microsoft Research India), Sreeram Kannan (University of Washington), Cari Kaufman (UC Berkeley), Lap-Chi Lau (The Chinese University of Hong Kong), Nati Linial (Hebrew University of Jerusalem), Mike Luby (Qualcomm Inc), Páll Melsted (University of Iceland), Olgica Milenkovic (University of Illinois, Urbana-Champaign), Andrea Montanari (Stanford University), Elchanan Mossel (UC Berkeley), Chandra Nair (The Chinese University of Hong Kong), Krishna Narayanan (Texas A&M University), Mesrob Ohannessian (UC San Diego), Alon Orlitsky (UC San Diego), Lior Pachter (UC Berkeley), Henry Pfister (Texas A&M University), Toniann Pitassi (University of Toronto), Jaikumar Radhakrishnan (Tata Institute of Fundamental Research), Kannan Ramchandran (UC Berkeley), Gireeja Ranade (Microsoft Research), Anup Rao (University of Washington), Ran Raz (Weizmann Institute), Meisam Razaviyayn (Stanford University), Thomas Richardson (Qualcomm Inc), Atri Rudra (SUNY Buffalo), Anant Sahai (UC Berkeley), Narayana Santhanam (University of Hawaii), Leonard Schulman (California Institute of Technology), Martha Sideri (Athens University of Economics and Business), Ali Sinop (Institute for Advanced Study, Princeton), Emina Soljanin (Bell Labs), Chang Ho Suh (KAIST), David Tse (Stanford University; co-chair), Rüdiger Urbanke (Ecole Polytechnique Fédérale de Lausanne), Sergio Verdú (Princeton University), Jan Vondrák (Stanford University), Martin Wainwright (UC Berkeley), Mary Wootters (University of Michigan), Sergey Yekhanin (Microsoft Research), Bin Yu (UC Berkeley), David Zuckerman (University of Texas, Austin)

Research Fellows:

Mahdi Cheraghchi (Massachusetts Institute of Technology; Qualcomm Research Fellow), Klim Efremenko (University of Chicago), Victoria Kostina (California Institute of Technology), Shannon McCurdy (UC Berkeley), Samet Oymak (UC Berkeley), Yury Polyanskiy (Massachusetts Institute of Technology), Benjamin Rossman (National Institute of Informatics), Eren Şaşoğlu (UC Berkeley), Ilan Shomorony (UC Berkeley), Li-Yang Tan (Columbia University; Microsoft Research Fellow), Yihong Wu (University of Illinois, Urbana-Champaign)

Visiting Graduate Students and Postdocs:

Reza Abbasi-Asl (UC Berkeley), Payam Delgosha (UC Berkeley), Moein Falahatgar (UC San Diego), Ankit Garg (Princeton University), Ashkan Jafarpour (UC San Diego), Varun Jog (UC Berkeley), Kangwook Lee (UC Berkeley), Marco Mondelli (Ecole Polytechnique Fédérale de Lausanne), Vidya Muthukumar (UC Berkeley), Ashwin Pananjady (UC Berkeley), Ramtin Pedarsani (UC Berkeley), Dheeraj Pichapati (UC San Diego), Miklos Racz (UC Berkeley), K. V. Rashmi (UC Berkeley), Aviad Rubinstein (UC Berkeley), Nihar Shah (UC Berkeley), Ananda Suresh (UC San Diego), Ameya Velingker (Carnegie Mellon University), Carol Wang (Carnegie Mellon University), Omri Weinstein (Princeton University)


Jan. 13Jan. 16, 2015


Venkat Guruswami (Carnegie Mellon University), David Tse (Stanford University)
Feb. 9Feb. 13, 2015


Alex Dimakis (University of Texas, Austin; co-chair), Mike Luby (Qualcomm Inc; co-chair), Thomas Richardson (Qualcomm Inc), Rüdiger Urbanke (Ecole Polytechnique Fédérale de Lausanne)
Mar. 16Mar. 20, 2015


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


Jaikumar Radhakrishnan (Tata Institute of Fundamental Research; chair), Mark Braverman (Princeton University), Venkat Guruswami (Carnegie Mellon University), Ran Raz (Weizmann Institute)
Jun. 6Jun. 9, 2016


Venkat Guruswami (Carnegie Mellon University), David Tse (Stanford University)

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