Introduction (2 lectures)
Cryptography and complexity (4 lectures)
Interactive proofs, PCP, inapproximability (4 lectures)
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 midterm 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.
Introduction (2 lectures)
(15/09 AR) Probabilistic complexity classes, Chernoff bounds, Polynomial Identity Testing:
scribe notes
(22/09 AR) The power of randomization : approximate rounding, approximate counting:
scribe notes
Interaction (2 lectures)

(06/10 IK) Interactive proofs, Zero Knowledge:
notes
Core results 1 (1 lecture)

Communication complexity (3 lectures)

(10/11 AR) Randomized communication complexity and information complexity:
scribe notes
(17/11 AR) Multiparty communication
Midterm exam on December 1st. All handwritten notes are allowed during the exam, as well as course notes provided on this webpage.
Learning Theory (2 lectures)
(08/12 IK) Learning framework, Occam's razor, computational and statistical complexity of learning:
notes
(15/12 IK) Learning through the Fourier Expansion, Lowdegree Learning, GoldreichLevin algorithm:
notes
Sublinear algorithms (4 lectures)
(05/01 FM) Search using random walks (application to stundirected connectivity, kSAT):
notes
Homework 2 to do by 01/19
(19/01 FM) Property testing (low degree polynomials, kcolorability, regular languages):
notes
(26/01 FM) Streaming algorithms (frequency moments, frequent items, wellparenthized expressions):
notes
(02/02 FM) Lower bounds on streaming algorithms (using communication complexity and information theory):
notes
Core results 2 (2 lectures)
(09/02 SP) Nonuniform lower bounds (circuits classes, polynomial hierarchy, interactive protocols): chapter 11 of book
Complexité Algorithmique
(16/02 FM) Expanders, construction and applications (derandomization and undirected stconnectivity):
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'.
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.
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.
I. Kerenidis  DR  CNRS  LIAFA 
F. Magniez  DR  CNRS  LIAFA 
S. Laplante  PR  Paris 7  LIAFA 
S. Perifel  MC  Paris 7  LIAFA 
A. Rosén  DR  CNRS  LIAFA 
M. de Rougemont  PR  Paris 2  LIAFA 
M. Santha  DR  CNRS  LIAFA 
H. Wee  CR  CNRS  ENS 