The Information Complexity and Appliations workshop was part of the STOC'13 workshops. It was held on Saturday, June 1, 2013, 8:30am-3:30pm.
- Mark Braverman, Princeton University;
- Amit Chakrabarti, Dartmouth College;
- Toniann Pitassi, University of Toronto;
- David Woodruff, IBM Research.
Program with abstracts
- In this tutorial we will discuss information theory and its connections to communication complexity. We will start with classical results by Shannon for non-interactive communication, and will then move on to more modern connections to interactive communication. We will discuss the notions of information complexity, interactive compression, and their connections to direct sum and direct product questions in communication complexity.
10:00-10:30 Morning break
10:30-11:20 Amit Chakrabarti "Applications of information complexity I". Slides [pdf]
- Information complexity was invented as a technique to prove a very specific direct sum result in communication complexity. Over the next decade, the notion of information complexity has been generalized, extended, and refined, leading to the rich theory we see today. I shall survey the key stages of this development, focusing on concrete lower bound questions that spurred it: both inside communication complexity and from applications in data streams and data structures.
- I will discuss recent applications of information complexity in compressed sensing, data streams, distributed computation, and sketching. I will also mention open problems in information complexity inspired by some of these areas.
12:15-2:00 Lunch break
- I will discuss several notions of privacy (including differential privacy and privacy-approximation ratio) within the context of communication complexity, and their very close relationship with information complexity. Through this connection, we will apply information complexity methods to prove trade-offs between privacy, efficiency, and accuracy in various settings.
3:00-3:30 Open problems session
3:30-4:00 Afternoon break