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. Possible topics include: 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

Lecture notes (read only link)

Tentative schedule. Eight lectures will be given out of these possible dates. Content is likely to change.

• September 17 Decision trees, Certificate complexity (See Shalev Ben David, lecture 1)
• September 24 Sensitivity and block sensitivity. Polynomial degree. symmetrization. Midrijanis's theorem. (See Shalev Ben David, lecture 5)
• October 1 Fractional block sensitivity and fractional certificates. LP duality. Shalev Ben David, lecture 2, sections 2.2-2.4
• October 8 Classical and quantum adversary bounds. Shalev Ben David, lecture 3

• October 15 Deterministic model. Lower bounds: fooling set, rectangle bound, rank. Equality function. Circuits.
• October 22 Randomized communication models. Yao min-max. Newman's theorem. Lower bounds for Disjointness and equality. Private and public randomness.
• October 29 (Fall break)
• November 5 (?)
• November 12 Information complexity. Multiparty.
• November 19 (?) Applications to algorithms. Streaming algorithms, distributed algorithms. One-way communication.

Exam (most likely) December 3rd

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

• Shalev Ben David Lecture notes
• Complexity Measures and Decision Tree Complexity, Harry Buhrman and Ronald de Wolf

Additional material not covered in lecture notes

• Exact quantum query complexity for total Boolean functions Gatis Midrijanis

• Topics in Circuit complexity lecture notes, Ryan O’Donnell
• A Brief Introduction to Fourier Analysis on the Boolean Cube, Ronald de Wolf
• Analysis of Boolean Functions, Ryan O'Donnell

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

Books may be available through your university library. For students registered at Université Paris Cité, access via proxy Cambridge University Press. Search for the book, then click Access through your institution. Select Université Paris Cité. Connect with your university credentials and allow your credentials to be transmitted. You may need to search for the book again. Good luck.