At some point the bite-sized series will get to communication complexity and its applications to proving data stream lower bounds. However, at the current rate of posting this will be some time in early 2016 (just as well proofs don’t expire). In case you don’t have that much patience, I wanted to mention two recent surveys/tutorials I just came across.
- Lower bounds in Communication Complexity by Lee and Shraibman
- Information Complexity: A Tutorial by Jayram
Update. See also the slides from the “Communication and Information in Complexity” day at the recent Barriers 2 workshop. (Thanks Paul!)