Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Randomness in Complexity (48h, 6 ECTS)

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

Course Outline 2015-2016

  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

Objectives

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.

Lectures Outline

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.

Course Language

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.

Relevant Courses

Pre-requisites

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.

Stages/Internships

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

Bibliography

  • 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.

Équipe pédagogique

I. KerenidisDRCNRSLIAFA
F. MagniezDRCNRSLIAFA
S. LaplantePRParis 7LIAFA
S. PerifelMCParis 7LIAFA
A. RosénDRCNRSLIAFA
M. de RougemontPRParis 2LIAFA
M. SanthaDRCNRSLIAFA
H. WeeCRCNRSENS
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA