Information Theory in Complexity Theory and Combinatorics

Program

Information Theory

Location

Calvin Lab Auditorium

Date

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

Back to calendar

Click on the titles of individual talks for abstract, slides and archived video.

All events take place in the Calvin Lab Auditorium.

9 – 9:25 a.m.

Coffee and Check-In

9:25 – 9:30 a.m.

Opening Remarks

9:30 – 10:45 a.m.

Tutorial on Coding for Interactive Communication: Introduction and Overview

Anup Rao (University of Washington)

10:45 – 11:15 a.m.

Break

11:15 – 11:45 a.m.

Exponential Separation of Information and Communication

Gillat Kol (Institute for Advanced Study, Princeton)

11:45 a.m. – 12:15 p.m.

Small Value Parallel Repetition for General Games

Ankit Garg (Princeton University)

12:15 – 1:30 p.m.

Lunch

1:30 – 2 p.m.

Answering FAQs in CSPs, PGMs, Databases, Logic and Matrix Operations

/node/12002

2 – 2:30 p.m.

Streaming Lower Bounds for Approximating MAX-CUT

Michael Kapralov, IBM T.J. Watson Research Center

2:30 – 3 p.m.

Extended Formulations and Information Complexity

Ankur Moitra, Massachusetts Institute of Technology

3 – 3:30 p.m.

Break

3:30 – 4 p.m.

Welfare Maximization with Limited Interaction: Information and Communication in Economics

Omri Weinstein (Princeton University)

4 – 4:30 p.m.

A New Look at Gallager's Bounds

Nati Linial (Hebrew University of Jerusalem)

5 – 6 p.m.

Reception

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:45 a.m.

Tutorial on Efficient Coding for Interactive Communication via List Decoding

Bernhard Haeupler, Carnegie Mellon University

10:45 – 11:15 a.m.

Break

11:15 – 11:45 a.m.

Relative Discrepancy Does Not Separate Information and Communication Complexity

Sophie Laplante, Université Paris Diderot

11:45 a.m. – 12:15 p.m.

Internal Compression of Protocols to Entropy

Shay Moran, Technion Israel Institute of Technology

12:15 – 1:30 p.m.

Lunch

1:30 – 2 p.m.

Lucky Talk: Exponential Separation of Information and Communication

Gillat Kol (Institute for Advanced Study, Princeton)

2 – 2:30 p.m.

Information Complexity for Multi-Party NIH Communication

Rotem Oshman, Tel Aviv University

2:30 – 3 p.m.

Upper Bound on List-decoding Radius of Binary Codes

Yury Polyanskiy (Massachusetts Institute of Technology)

3 – 3:30 p.m.

Break

3:30 – 4 p.m.

On the Communication Complexity of Sparse Set Disjointness

Gábor Tardos, Alfréd Rényi Institute of Mathematics

4 – 4:30 p.m.

Some Novel Computational Models to Think About

D. Sivakumar, Google Research

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:45 a.m.

Tutorial on Capacity in Coding for Interactive Communication

Ran Raz (Weizmann Institute), Bernhard Haeupler, Carnegie Mellon University

10:45 – 11:15 a.m.

Break

11:15 – 11:45 a.m.

An Information Theoretic View of Hypercontractivity

Ehud Friedgut, Weizmann Institute

11:45 a.m. – 12:15 p.m.

Equality, Revisited

Hartmut Klauck, Nanyang Technological University

12:15 – 1:30 p.m.

Lunch

1:30 – 2 p.m.

Lucky Talk: Upper Bound on List-decoding Radius of Binary Codes

Yury Polyanskiy (Massachusetts Institute of Technology)

2 – 2:30 p.m.

Non-Signalling Parallel Repetition Using de Finetti Reductions

Thomas Vidick (California Institute of Technology)

2:30 – 3 p.m.

Limits to Efficient Preprocessing

Andrew Drucker (University of Chicago)

3 – 3:30 p.m.

Break

3:30 – 4 p.m.

Parallel Repetition for Entangled Games via Fast Quantum Search

4 – 4:30 p.m.

Do Read Errors Matter for DNA Assembly?

Thomas Courtade (UC Berkeley)

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:45 a.m.

Tutorial on List Decodable Coding Schemes and Interactive Communication in Networks

Klim Efremenko (Tel Aviv University), Ran Gelles, Princeton University

10:45 – 11:15 a.m.

Break

11:15 – 11:45 a.m.

Information Theory and Polyhedral Combinatorics

Sebastian Pokutta, Georgia Institute of Technology

11:45 a.m. – 12:15 p.m.

Information Theory and Additive Combinatorics

Mokshay Madiman, University of Delaware

12:15 – 1:30 p.m.

Lunch

1:30 – 2 p.m.

Lucky Talk: An Information Theoretic View of Hypercontractivity

Ehud Friedgut, Weizmann Institute

2 – 2:30 p.m.

On Parallelizing Streaming Algorithms

Makrand Sinha, University of Washington

2:30 – 3 p.m.

Streaming Interactive Proofs and Arthur-Merlin Communication

Amit Chakrabarti (Dartmouth College)

3 – 3:30 p.m.

Break

3:30 – 4 p.m.

A Communication Game Approach to the Sensitivity Conjecture

Mike Saks, Rutgers University

4 – 4:30 p.m.

Deterministic Communication vs. Partition Number

Toni Pitassi (University of Toronto)

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10 a.m.

Interactive and Amortized Communication – An Information Theoretic Perspective

Alon Orlitsky (UC San Diego)

10 – 10:30 a.m.

Lucky Talk: A Communication Game Approach to the Sensitivity Conjecture

Mike Saks, Rutgers University

10:30 – 11 a.m.

Break

11 – 11:30 a.m.

Counting Distinct Elements in the Message Passing Model

David Woodruff (Carnegie Mellon University)

11:30 a.m. – 12 p.m.

Superlinear Lower Bounds for Multipass Graph Processing

Krzysztof Onak, IBM T.J. Watson Research Center

12 – 1:30 p.m.

Lunch

1:30 – 2 p.m.

Tribes is Hard in the Message Passing Model

Arkadev Chattopadhyay (Tata Institute of Fundamental Research)

2 – 2:30 p.m.

Combinatorial Proofs of Concentration Bounds

Thomas Holenstein (ETH Zürich)

2:30 – 3 p.m.

How to Compress Asymmetric Communication

Sivaramakrishnan Natarajan Ramamoorthy, University of Washington

3 – 3:30 p.m.

Break

3:30 – 4 p.m.

On Geometric Measures for Information Complexity

T.S. Jayram (IBM Almaden)

4 – 4:30 p.m.

Information Complexity is Computable

Mark Braverman (Princeton University)