Skip to main content
Search
Utility navigation
Calendar
Contact
Login
MAKE A GIFT
Main navigation
Home
Programs & Events
Research Programs
Workshops & Symposia
Public Lectures
Research Pods
Internal Program Activities
Algorithms, Society, and the Law
People
Scientific Leadership
Staff
Current Long-Term Visitors
Research Fellows
Postdoctoral Researchers
Scientific Advisory Board
Governance Board
Industry Advisory Council
Affiliated Faculty
Science Communicators in Residence
Law and Society Fellows
Participate
Apply to Participate
Plan Your Visit
Location & Directions
Postdoctoral Research Fellowships
Law and Society Fellowships
Science Communicator in Residence Program
Circles
Breakthroughs Workshops and Goldwasser Exploratory Workshops
Support
Annual Fund
Funders
Industrial Partnerships
News & Videos
News
Videos
About
Image
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
Breadcrumb
Home
Workshop & Symposia
Schedule
Secondary tabs
The Workshop
Schedule
Videos
Click on the titles of individual talks for abstract, slides and archived video.
All events take place in the Calvin Lab Auditorium.
Monday, Apr. 20, 2015
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
Tuesday, Apr. 21, 2015
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
Wednesday, Apr. 22, 2015
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)
Thursday, Apr. 23, 2015
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 (Columbia University)
Friday, Apr. 24, 2015
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)
Share this page
Copy URL of this page
link to homepage
Close
Main navigation
Home
Programs & Events
Research Programs
Workshops & Symposia
Public Lectures
Research Pods
Internal Program Activities
Algorithms, Society, and the Law
People
Scientific Leadership
Staff
Current Long-Term Visitors
Research Fellows
Postdoctoral Researchers
Scientific Advisory Board
Governance Board
Industry Advisory Council
Affiliated Faculty
Science Communicators in Residence
Law and Society Fellows
Participate
Apply to Participate
Plan Your Visit
Location & Directions
Postdoctoral Research Fellowships
Law and Society Fellowships
Science Communicator in Residence Program
Circles
Breakthroughs Workshops and Goldwasser Exploratory Workshops
Support
Annual Fund
Funders
Industrial Partnerships
News & Videos
News
Videos
About
Utility navigation
Calendar
Contact
Login
MAKE A GIFT
link to homepage
Close
Search