WikiMPRI

Course manager: Frédéric Magniez ( LIAFA)

1. Introduction (2 lectures)
2. Cryptography and complexity (4 lectures)
3. Interactive proofs, PCP, inapproximability (4 lectures)
4. Other topics among online algorithms, property testing, algorithmic game theory, learning theory (2 lectures)

Teachers: I. Kerenidis, F. Magniez, S. Perifel, A. Rosén.
Lectures will be on Tuesdays from 12:45 to 15:45, room 2036.
There will be a mid-term exam on December 1st and a final exam on March 8th. All handwritten notes are allowed during the exam, as well as course notes provided on this webpage.
Homeworks are also planned.

Homework 1 to do by 03/11
Homework 2 to do by 01/19

The goal of the course is to provide a strong background to students interested in randomized aspects of computational complexity and its applications to cryptography, interactive models, communication, and algorithms.

Period 1: September 15 to November 17. No classes on October 20 and 27. Exam on December 1st.
Period 2: December 8 to February 9. No classes on January 12 and February 23. Exam on March 8th.

1. Introduction (2 lectures)
   1. (15/09 AR) Probabilistic complexity classes, Chernoff bounds, Polynomial Identity Testing: scribe notes
   2. (22/09 AR) The power of randomization : approximate rounding, approximate counting: scribe notes
2. Interaction (2 lectures)
   1. (29/09 SP) Interactive proofs: chapter 10 of book Complexité Algorithmique
   2. (06/10 IK) Interactive proofs, Zero Knowledge: notes
3. Core results 1 (1 lecture)
   1. (13/10 IK) PCP with exponential proofs: notes
      Homework 1 to do by 03/11
4. Communication complexity (3 lectures)
   1. (03/11 AR) Communication complexity: scribe notes
   2. (10/11 AR) Randomized communication complexity and information complexity: scribe notes
   3. (17/11 AR) Multiparty communication

Mid-term exam on December 1st. All handwritten notes are allowed during the exam, as well as course notes provided on this webpage.

1. Learning Theory (2 lectures)
   1. (08/12 IK) Learning framework, Occam's razor, computational and statistical complexity of learning: notes
   2. (15/12 IK) Learning through the Fourier Expansion, Low-degree Learning, Goldreich-Levin algorithm: notes
2. Sublinear algorithms (4 lectures)
   1. (05/01 FM) Search using random walks (application to st-undirected connectivity, k-SAT): notes
      Homework 2 to do by 01/19
   2. (19/01 FM) Property testing (low degree polynomials, k-colorability, regular languages): notes
   3. (26/01 FM) Streaming algorithms (frequency moments, frequent items, well-parenthized expressions): notes
   4. (02/02 FM) Lower bounds on streaming algorithms (using communication complexity and information theory): notes
3. Core results 2 (2 lectures)
   1. (09/02 SP) Non-uniform lower bounds (circuits classes, polynomial hierarchy, interactive protocols): chapter 11 of book Complexité Algorithmique
   2. (16/02 FM) Expanders, construction and applications (derandomization and undirected st-connectivity): notes

Final exam on March 8th. All handwritten notes are allowed during the exam, as well as course notes provided on this webpage.

Some lectures will be in English, and others in French with English upon request. Homework assignments and exams will be available in English and French, at the students' request, and can be written in either language.

The following is a coherent list of courses on the thematic 'Algorithms and Complexity'.

• 2-11-1 Advanced Algorithms
• 2-11-2 Randomness in Complexity
• 2-12-1 Techniques in Cryptography and Cryptanalysis
• 2-13-2 Error correcting codes and applications to cryptography
• 2-18-1 Distributed algorithms for the networks
• 2-18-2 Algorithmique distribuée avec mémoire partagée
• 2-24-1 Optimisation
• 2-29-1 Graph algorithms
• 2-33-1 Theory of Computations
• 2-34-1 Quantum information and applications
• 2-38-1 Algorithms and combinatorics for geometric graphs

Basics of complexity theory (classes P, NP, etc.). Even if the course is breakable, students attending the second half of the class are expecting to have attended the first half.

Internships in the area of Complexity Theory are available. Please contact the Algorithms and Complexity group of LIAFA

• Computational complexity: A modern approach. Sanjeev Arora and Boaz Barak. Cambridge University Press, 2010.
• Complexité Algorithmique, Sylvain Perifel. Ellipses, 2014. Lien pdf.
• Computational Complexity. C. H. Papadimitriou. Addison Wesley, 1994.
• Communication Complexity. Eyal Kushilevitz and Noam Nisan. Cambridge University Press, 2006.