2015 Barbados Workshop on Computational Complexity

2015 Barbados Workshop on Computational Complexity


The 27th McGill Invitational Workshop on Computational Complexity will be held at Bellairs Research Institute of McGill University, Holetown, St. James, Barbados, West Indies from February 20th to 27th, 2015. Participants can arrive either on February 20th or the 21st. Lectures will start February 22nd and end on the 26th. The subject of this year's workshop will be Information, Communication Complexity, and Interactive Coding.



Speaker:
Mark Braverman
Princeton University
Information, Communication Complexity, and Interactive Coding

The goal will be to cover basic information theory and its connections to communication complexity, hardness amplification, and interactive coding theory. Tentatively, the mini-course will have three parts:

  1. The first part will be a detailed tutorial on basic information theory for CS researchers, with a view to making it a tool you can apply on a daily basis;
  2. The second part will deal with information complexity, its connections to communication complexity, to direct sum/product theorems and to hardness amplification (parallel repetition);
  3. The third part will deal with interactive coding theory, including a brief overview of error-correcting codes over interactive channels, and our understanding of interactive compression.

In terms of connections to Mike's course of 2011, it will be more organized theory-wise (our understanding improved a lot in the past 4 years), but less branched in terms of applications.


Important Information for Participants