Provide tools to prove lower bounds for algorithms and in various models of computation. Prerequisites: No formal prerequisites for this course, it should be accessible to all M2 MPRI students. It is expected that students have some basic notions of algorithms, algorithmic complexity (upper bounds, big O notation) and complexity theory, including time and space complexity, as well as some basic probability and linear algebra. Some knowledge of linear programming and LP duality would be useful but basics will be recalled. Knowledge of quantum computing is welcome but not required.

The course will follow (for the most part) the second part of the textbook Computational Complexity: A Modern Approach by Arora and Barak. This is considered to be the standard reference on Complexity Theory.

Lower bound techniques including certificate complexity, sensitivity, block sensitivity, polynomial degree and approximate degree. Special function classes including symmetric functions. Randomized versus distributional complexity (Yao min-max theorem). Quantum query complexity lower bound techniques: adversary bounds and polynomial degree. Applications to algorithmic time complexity lower bounds.

Lower bound techniques including rank, discrepancy, partition bounds. Randomized communication complexity. Distributional versus randomized complexity (Yao min-max theorem). Shared coins versus private randomness (Newman's theorem). Information complexity. Quantum lower bounds. Applications to lower bounds for various models including for streaming algorithms, distributed computing, formula size and circuit depth.

Class format : 3 hours per week x 8 weeks, including problem sessions and occasional guest lectures.

Schedule : Wednesdays 12:45-15:45 in room 1002, starting September 17

Evaluation :

• Exercises and possibly presentation of a part of a paper (depending on number of students) 25%
• Written exam 75% on Dec 3rd.

Lecturers:

• Adi Rosen : adiro@irif.fr
• Sophie Laplante : laplante@irif.fr

• Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak.
• Boolean Function Complexity, Stasys Jukna (Login : Boole pw : Shannon)

• Boolean function analysis, Ryan O'Donnell
• A Brief Introduction to Fourier Analysis on the Boolean Cube, Ronald de Wolf
• Complexity Measures and Decision Tree Complexity, Harry Buhrman and Ronald de Wolf
• Topics in Circuit complexity lecture notes, Ryan O’Donnell https://people.csail.mit.edu/rrw/cs354.html

• Communication Complexity, Eyal Kushilevitz and Noam Nisan
• Lower Bounds in Communication Complexity, Troy Lee and Adi Schraibman
• Communication Complexity and Applications, Anup Rao and Amir Yehudayoff
• Communication Complexity (for Algorithm Designers), Tim Roughgarden, lecture notes