Information Theory in Complexity Theory and Combinatorics

Program

Information Theory

Location

Calvin Lab Auditorium

Date

Monday, Apr. 20 – Friday, Apr. 24, 2015

About

This workshop focuses on the applications of information theoretic techniques in communication complexity and combinatorics.

Communication complexity studies the communication needed to compute functions whose inputs are distributed across several agents. There are deep connections between communication complexity and other areas of computation, such as circuits, data structures, streaming, space bounded computation, cryptography and optimization. Over the past five years, there have been significant advances in the role of information in the study of communication problems. For example, the role of information complexity and message compression is now much better understood. In the setting of these results, one-shot bounds play a greater role than traditional asymptotic results, and the resulting techniques may be of general interest in the information theory community. Information theoretic techniques have had relatively little success in multiparty communication (as opposed to two-party communication), which presents an opportunity for comparing them with other analytic techniques that have been more successful. In addition, recent work has revived interest in the connection between communication complexity and the existence of linear programming based solutions to optimization problems. This combined body of work, and the open problems there, will form an important component of this workshop. Another component centers on information theoretic lower bounds in streaming and data structures, where there has been an explosion of recent results.

Finally, information theoretic ideas have been employed to study problems in graph theory and combinatorics, notably in counting problems such as counting independent sets in bipartite graphs, Steiner systems, matchings etc. In addition, many results in areas such as hypercontractivity estimates, concentration inequalities and additive combinatorics can be placed in an information theoretic context. This provides scope for useful interactions between experts in information theory and combinatorics.

All talks will be recorded. Enquiries may be sent to the organizers at this address.

Chairs/Organizers

Jaikumar Radhakrishnan (Tata Institute of Fundamental Research; chair)

Mark Braverman (Princeton University)

Venkatesan Guruswami (Simons Institute, UC Berkeley)

Ran Raz (Weizmann Institute)

Invited Participants

Venkat Anantharam (UC Berkeley), Alexandr Andoni (UC Berkeley), Elaine Angelino (UC Berkeley), Peter Bartlett (UC Berkeley), Mark Braverman (Princeton University), Guy Bresler (Massachusetts Institute of Technology), Amit Chakrabarti (Dartmouth College), Sourav Chakraborty (Chennai Mathematical Institute), Arkadev Chattopadhyay (Tata Institute of Fundamental Research), Mahdi Cheraghchi (Massachusetts Institute of Technology), Thomas Courtade (UC Berkeley), Marco Dalai (University of Brescia), Suhas Diggavi (UCLA), Andrew Drucker (University of Edinburgh), Cynthia Dwork (Microsoft Research), Klim Efremenko (University of Chicago), Saleh Elmohamed (UC Berkeley and Cornell University), Moein Falahatgar (UC San Diego), Vitaly Feldman (IBM Almaden), Ehud Friedgut (Weizmann Institute), Anna Gál (University of Texas, Austin), Ankit Garg (Princeton University), Ran Gelles (Princeton University), Parikshit Gopalan (Microsoft Corporation), Venkatesan Guruswami (Carnegie Mellon University), Bernhard Haeupler (Carnegie Mellon University), Prahladh Harsha (Tata Institute of Fundamental Research), Thomas Holenstein (ETH Zuerich), Ashkan Jafarpour-Koujahi (UC San Diego), Rahul Jain (National University of Singapore), Adel Javanmard (Stanford University and UC Berkeley), Ravindran Kannan (Microsoft Research India), Sreeram Kannan (University of Washington), Michael Kapralov (IBM T.J. Watson Research Center), Cari Kaufman (UC Berkeley), Hartmut Klauck (Nanyang Technological University and Centre for Quantum Technologies), Gillat Kol (Institute for Advanced Study, Princeton), Victoria Kostina (Princeton University), Lap-Chi Lau (University of Waterloo), Troy Lee (Nanyang Technological University), Kangwook Lee (UC Berkeley), Nathan Linial (Hebrew University of Jerusalem), Michael Luby (Qualcomm Inc.), Chandrasekhar Madhavan Nair (Chinese University of Hong Kong), Mokshay Madiman (University of Delaware), Shannon Mccurdy (UC Berkeley), Páll Melsted (University of Iceland), Olgica Milenkovic (University of Illinois, Urbana-Champaign), Ankur Moitra (Massachusetts Institute of Technology), Shay Moran (Technion Israel Institute of Technology), Sivaramakrishnan Natarajan Ramamoorthy (University of Washington), Ashwin Nayak (University of Waterloo), Huy Nguyen (Princeton University), Mesrob Ohannessian (UC San Diego), Krzysztof Onak (IBM T.J. Watson Research Center), Alon Orlitsky (UC San Diego), Rotem Oshman (Tel Aviv University), Samet Oymak (UC Berkeley), Lior Pachter (UC Berkeley), Venkatadheeraj Pichapati (UC San Diego), Toniann Pitassi (University of Toronto), Sebastian Pokutta (Georgia Institute of Technology), Yury Polyanskiy (Massachusetts Institute of Technology), Miklos Racz (UC Berkeley), Jaikumar Radhkrishnan (Tata Institute of Fundamental Research), Kannan Ramchandran (UC Berkeley), Gireeja Ranade (UC Berkeley), Anup Rao (University of Washington), Ran Raz (Weizmann Institute and Institute for Advanced Study, Princeton), Meisam Razaviyayn (Stanford University), Benjamin Rossman (National Institute of Informatics), Thomas Rothvoss (University of Washington), Aviad Rubinstein (UC Berkeley), Atri Rudra (SUNY Buffalo), Anant Sahai (UC Berkeley), Mike Saks (Rutgers University), Narayana Santhanam (University of Hawaii), Eren Şaşoğlu (UC Berkeley), Nihar Shah (UC Berkeley), Ilan Shomorony (UC Berkeley), Makrand Sinha (University of Washington), Ali Sinop (Institute for Advanced Study, Princeton), D. Sivakumar (Google Research), Emina Soljanin (Bell Labs), Ananda Suresh (UC San Diego), Li-Yang Tan (Columbia University), Gábor Tardos (Alfréd Rényi Institute of Mathematics), Jayram Thathachar (IBM Almaden), David Tse (Stanford University), Rüdiger Urbanke (École Polytechnique Fédérale de Lausanne), Ameya Velingker (Carnegie Mellon University), Sergio Verdú (Princeton University), Thomas Vidick (California Institute of Technology), Jan Vondrák (IBM Almaden), Martin Wainwright (UC Berkeley), Carol Wang (Carnegie Mellon University), Omri Weinstein (Princeton University), David Woodruff (IBM Almaden), Mary Wootters (Carnegie Mellon University), Yihong Wu (University of Illinois, Urbana-Champaign), Sergey Yekhanin (Microsoft Research), Bin Yu (UC Berkeley), Henry Yuen (Massachusetts Institute of Technology), and David Zuckerman (University of Texas, Austin).