|
|
Main topics
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.
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.
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
Research internships are available. Please contact the instructor.
The following is a coherent list of courses on the thematic 'Algorithms and Complexity'.
| F. Magniez | DR | CNRS | IRIF |
| C. Mathieu | DR | CNRS | IRIF |
| S. Périfel | MC | Paris 7 | IRIF |
| A. Rosen | DR | CNRS | IRIF |
| M. de Rougemont | PR | Paris 2 | IRIF |
| A. Vladu | CR | CNRS | IRIF |
Main topics
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:
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.
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.
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.
 Please check the course webpage for up to date information.
15/09: Basics of optimization. Learning with experts. Algorithmic applications (Plotkin-Shmoys-Tardos, oblivious routings)
22/09: J-trees, dynamic minimum spanning tree. Fast graph cut approximators using J-trees.
29/09: Iterative methods for solving linear systems. Preconditioning.
06/10: no lecture
13/10: Laplacian matrices and linear systems. Equivalence to electrical flows. Matrix Chernoff and spectral sparsification.
20/10: Spectral sparsification (continued). Augmented tree preconditioners.
27/10: Algorithmic graph theory using electrical flows. Interior point methods.
03/10: Interior point methods (continued).
10/11: Wrap-up, open problems.
|