Workshops

Spring 2015

Information Theory in Complexity Theory and Combinatorics

Apr 20, 2015 to Apr 24, 2015

Return to event »

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

All events take place in the Calvin Lab Auditorium.

Monday, April 20th, 2015
9:00 am–9:25 am		Coffee and Check-In
9:25 am–9:30 am		Opening Remarks
9:30 am–10:45 am		Tutorial on Coding for Interactive Communication: Introduction and Overview Anup Rao, University of Washington
10:45 am–11:15 am		Break
11:15 am–11:45 am		Exponential Separation of Information and Communication Gillat Kol, Institute for Advanced Study, Princeton
11:45 am–12:15 pm		Small Value Parallel Repetition for General Games Ankit Garg, Princeton University
12:15 pm–1:30 pm		Lunch
1:30 pm–2:00 pm		Answering FAQs in CSPs, PGMs, Databases, Logic and Matrix Operations Atri Rudra, SUNY Buffalo
2:00 pm–2:30 pm		Streaming Lower Bounds for Approximating MAX-CUT Michael Kapralov, IBM T.J. Watson Research Center
2:30 pm–3:00 pm		Extended Formulations and Information Complexity Ankur Moitra, Massachusetts Institute of Technology
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		Welfare Maximization with Limited Interaction: Information and Communication in Economics Omri Weinstein, Princeton University
4:00 pm–4:30 pm		A New Look at Gallager's Bounds Nati Linial, Hebrew University of Jerusalem
5:00 pm–6:00 pm		Reception

Tuesday, April 21st, 2015
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:45 am		Tutorial on Efficient Coding for Interactive Communication via List Decoding Bernhard Haeupler, Carnegie Mellon University
10:45 am–11:15 am		Break
11:15 am–11:45 am		Relative Discrepancy Does Not Separate Information and Communication Complexity Sophie Laplante, Université Paris Diderot
11:45 am–12:15 pm		Internal Compression of Protocols to Entropy Shay Moran, Technion Israel Institute of Technology
12:15 pm–1:30 pm		Lunch
1:30 pm–2:00 pm		Lucky Talk: Exponential Separation of Information and Communication Gillat Kol, Institute for Advanced Study, Princeton
2:00 pm–2:30 pm		Information Complexity for Multi-Party NIH Communication Rotem Oshman, Tel Aviv University
2:30 pm–3:00 pm		Upper Bound on List-decoding Radius of Binary Codes Yury Polyanskiy, Massachusetts Institute of Technology
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		On the Communication Complexity of Sparse Set Disjointness Gábor Tardos, Alfréd Rényi Institute of Mathematics
4:00 pm–4:30 pm		Some Novel Computational Models to Think About D. Sivakumar, Google Research

Wednesday, April 22nd, 2015
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:45 am		Tutorial on Capacity in Coding for Interactive Communication Ran Raz, Weizmann Institute and Institute for Advanced Study and Bernhard Haeupler, Carnegie Mellon University
10:45 am–11:15 am		Break
11:15 am–11:45 am		An Information Theoretic View of Hypercontractivity Ehud Friedgut, Weizmann Institute
11:45 am–12:15 pm		Equality, Revisited Hartmut Klauck, Nanyang Technological University
12:15 pm–1:30 pm		Lunch
1:30 pm–2:00 pm		Lucky Talk: Upper Bound on List-decoding Radius of Binary Codes Yury Polyanskiy, Massachusetts Institute of Technology
2:00 pm–2:30 pm		Non-Signalling Parallel Repetition Using de Finetti Reductions Thomas Vidick, California Institute of Technology
2:30 pm–3:00 pm		Limits to Efficient Preprocessing Andrew Drucker, University of Chicago
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		Parallel Repetition for Entangled Games via Fast Quantum Search Henry Yuen, Massachusetts Institute of Technology
4:00 pm–4:30 pm		Do Read Errors Matter for DNA Assembly? Thomas Courtade, UC Berkeley

Thursday, April 23rd, 2015
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:45 am		Tutorial on List Decodable Coding Schemes and Interactive Communication in Networks Klim Efremenko, Tel Aviv University and Ran Gelles, Princeton University
10:45 am–11:15 am		Break
11:15 am–11:45 am		Information Theory and Polyhedral Combinatorics Sebastian Pokutta, Georgia Institute of Technology
11:45 am–12:15 pm		Information Theory and Additive Combinatorics Mokshay Madiman, University of Delaware
12:15 pm–1:30 pm		Lunch
1:30 pm–2:00 pm		Lucky Talk: An Information Theoretic View of Hypercontractivity Ehud Friedgut, Weizmann Institute
2:00 pm–2:30 pm		On Parallelizing Streaming Algorithms Makrand Sinha, University of Washington
2:30 pm–3:00 pm		Streaming Interactive Proofs and Arthur-Merlin Communication Amit Chakrabarti, Dartmouth College
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		A Communication Game Approach to the Sensitivity Conjecture Mike Saks, Rutgers University
4:00 pm–4:30 pm		Deterministic Communication vs. Partition Number Toniann Pitassi, University of Toronto

Friday, April 24th, 2015
9:00 am–9:30 am		Coffee and Check-In
9:30 am–10:00 am		Interactive and Amortized Communication – An Information Theoretic Perspective Alon Orlitsky, UC San Diego
10:00 am–10:30 am		Lucky Talk: A Communication Game Approach to the Sensitivity Conjecture Mike Saks, Rutgers University
10:30 am–11:00 am		Break
11:00 am–11:30 am		Counting Distinct Elements in the Message Passing Model David Woodruff, IBM Almaden
11:30 am–12:00 pm		Superlinear Lower Bounds for Multipass Graph Processing Krzysztof Onak, IBM T.J. Watson Research Center
12:00 pm–1:30 pm		Lunch
1:30 pm–2:00 pm		Tribes is Hard in the Message Passing Model Arkadev Chattopadhyay, Tata Institute of Fundamental Research
2:00 pm–2:30 pm		Combinatorial Proofs of Concentration Bounds Thomas Holenstein, ETH Zürich
2:30 pm–3:00 pm		How to Compress Asymmetric Communication Sivaramakrishnan Natarajan Ramamoorthy, University of Washington
3:00 pm–3:30 pm		Break
3:30 pm–4:00 pm		On Geometric Measures for Information Complexity T.S. Jayram, IBM Almaden
4:00 pm–4:30 pm		Information Complexity is Computable Mark Braverman, Princeton University