Lecture 1: (Sept 12, Toni) Course overview, Deterministic, Randomized, Nondeterministic Complexity. Newman's theorem. Important functions (equality, set disjointness) and protocols for them. Lecture 2: (Sept 19, Toni) Deterministic Lower Bounds: Combinatorial Rectangles, The Fooling Set Method, The Rank Method, The Logrank Conjecture (Sept 26, cancelled) Lecture 3: (Oct 3, Toni) Randomized Lower Bounds: Distributional complexity and Yao's Theorem, The Discrepancy Method. Lecture 4: (Oct 10, Toni) Discrepancy continued, The Pattern Matrix (Dual Polynomial) Method. Applications of commmunication complexity lower bounds. Lecture 5: (Oct 17, Toni) Applications of Communication Complexity; Jain-Klauck paper: Characterizing Lower Bound Methods via Linear Programs. Lecture 6: (Oct 24) Student presentations on communication complexity Sandro Feuz and Mika Goos Lecture 7: (Oct 31, Toni and Lila) Information Complexity Introduction; Barak-Braverman-Chen-Rao paper: compressing protocols. Lecture 8: (Nov 7, Lila) Lower Bounds for Information Complexity via zero-communication protocols. (Kerenidis, Laplante, Lerays, Roland, Xiao paper) Lecture 9: (Nov 14) Student presentations on communication complexity and information complexity Lecture 10: (Nov 21, Lila) Finish student presentations if not completed. Approximate Privacy and Information Complexity Lecture 11: (Nov 28, Toni) Differential Privacy and Information Complexity, Course wrapup and open problems.