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

Randomness in Complexity (24h, 3 ECTS)

Course manager: Adrian Vladu (IRIF)

Course Outline 2024-2025

Main topics

  • Approximation Algorithms

Instructors

Organization

  • 8 lectures, each is 3 hours long.
  • Schedule is to be determined.
  • Lectures will be offered in English upon request.
  • There will be regular homework. Final grade will be max(exam, (homeworks + 2exam)/3)

Objectives

The common thread of the course is the use of randomness in algorithms and complexity. This year, the course will cover approximation algorithms.

Lectures Outline

  • Rounding: Knapsack, Bin packing, and scheduling
  • Randomized rounding of LP relaxations: set cover, submodular optimization, maximum satisfiability, multiway cut, maxcut in dense graphs
  • Primal-dual techniques: network design, multicut, facility location
  • Iterative rounding
  • Embedding metrics : Quadtree in Euclidean space, Bartal's embedding; Johnson-Lindenstrauss lemma for Dimension reduction
  • TSP : Christophides algorithm, Arora's approximation scheme in $\mathbb{R}^2$
  • Semi-definite programming: maxcut, unique games and other problems
  • Openning topics, e.g.: Local Search, Sketching, Online algorithms...

Pre-requisites

  • M1 level Algorithms
  • Standard background on Discrete Probability

Stages/Internships

Research internships are available. Please contact the instructors.

Bibliography

Relevant Courses

Previous Offerings

Course Outline 2023-2024

Main topics

  • Algorithms for societal problems

Instructor

Organization

  • 8 lectures, each is 3 hours long (see schedule)
  • Lectures will be on Thursdays at 16:15 pm, room 1002, starting 14/09.
  • Lectures will be offered in English.
  • Students may opt to give a short oral presentation during the course, for a possible bonus of 1 point for the final grade.
  • The final exam will on 30/11 be available in English and can be written in either English or French.

Objectives

The common thread of the course is the use of randomness in algorithms and complexity. This year, the course will cover algorithms for societal problems.

Lectures Outline

  • 14/09: Stable marriage and college admission
  • 21/09: Probabilistic model and analysis of Gale-Shapley algorithm
  • 28/09: LLMs
  • 05/10: no lecture
  • 12/10: Bias of linear regression ranking methods for prediction; speed-scaling algorithms for CPU energy conservation
  • 19/10: no lecture
  • 26/10: Fair division and cake cutting algorithms
  • 02/11: Redistricting, apportionment methods
  • 09/11: Kidney exchange program & probabilistic analysis of longest chain in Erdos-Renyi model
  • 16/11: Review exercises
  • 23/11: no lecture
  • 30/11: Final exam

Pre-requisites

  • M1 level Algorithms
  • Standard background on Discrete Probability

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

Course Outline 2022-23

Main topics

  • Continuous Methods in Combinatorial Optimization

Instructor

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.

Bibliography

 
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