Welcome to this course! Communication complexity is a computational model which captures communication cost between several parties to jointly compute a function. There are several players in the model with each having their own input. The goal to compute a joint function based on the inputs, while minimizing communication bits. Besides communication complexity itself, lower bounds in this model also capture many other computational models such as time-space tradeoffs for data structures, streaming algorithms, sketching algorithms, sub-linear time algorithms, and many more. This course will introduce several techniques to prove communication lower bounds as well as their applications to streaming lower bounds.
General Information:
Instructor: Jiapeng Zhang. ( jiapengz@usc.edu )
Time: Thursday 3:30 - 6:50 pm
Office hours: by appointments
Location: SOS B48.
Piazza: link.
Grading:
Two homework sets, each worth 25%. The homework can be done in a group of at most three students.
Presentation 50%.
Resources and Other Courses:
Mark Bun - Boston University (2019)
Shachar Lovett - UCSD (2019)
Alexander Sherstov - UCLA (2018)
Toni Pitassi - U. Toronto (2014)