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

Randomness in Complexity (24h, 3 ECTS)

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

Course Outline 2022-2023

Main topics

  • Continuous Methods in Combinatorial Optimization

Instructors

Organization

  • 8 lectures, each is 3 hours long (see schedule)
  • Lectures will be on Thursdays at 12:45 pm, room 1002, starting 15/09.
  • Lectures will be offered in English. Homework assignments and exams will be available in English and can be written in either English or French.
  • The final course grade will be the average of two grades:
    1. One grade results from a 3-hour final exam on December 1, at 12:45pm in Room 1002. The exam questions will be written in English and the answers may be written in French or in English, at the preference of the student taking the exam. All handwritten notes are allowed during the exam, as well as printouts of course notes provided on this webpage.
    2. The other grade evaluates a research-oriented project, chosen with the help of the instructor. Students may work in pairs. It can be in French or in English, at the preference of the students.
  • Light homework will be assigned. While this will not count towards your final grade, it is crucial to solve it in order to guarantee a good grade on the final exam.
  • More information will be periodically made available here.

Objectives

The common thread of the course is the use of randomness in algorithms and complexity. This year, the course will cover a series of ideas and techniques at the boundary between combinatorial and continuous optimization. In particular we will focus on graph algorithms, interpreted through the prism of continuous methods.

Lectures Outline

:!: Please check the course webpage for up to date information. :!:

  1. 15/09: Basics of optimization. Learning with experts. Algorithmic applications (Plotkin-Shmoys-Tardos, oblivious routings)
  2. 22/09: J-trees, dynamic minimum spanning tree. Fast graph cut approximators using J-trees.
  3. 29/09: Iterative methods for solving linear systems. Preconditioning.
  4. 06/10: no lecture
  5. 13/10: Laplacian matrices and linear systems. Equivalence to electrical flows. Matrix Chernoff and spectral sparsification.
  6. 20/10: Spectral sparsification (continued). Augmented tree preconditioners.
  7. 27/10: Algorithmic graph theory using electrical flows. Interior point methods.
  8. 03/10: Interior point methods (continued).
  9. 10/11: Wrap-up, open problems.

Pre-requisites

Linear algebra, basic algorithms, basic notions in probability. The class will move fairly quickly, so some mathematical maturity is required.

Stages/Internships

Research internships are available. Please contact the instructor.

Bibliography

Relevant Courses

Instructors

F. MagniezDRCNRSIRIF
C. MathieuDRCNRSIRIF
S. PérifelMCParis 7IRIF
A. RosenDRCNRSIRIF
M. de RougemontPRParis 2IRIF
A. VladuCRCNRSIRIF
 
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