Main topics

• Algorithms for societal problems

Instructor

• Claire Mathieu (IRIF)

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

• M1 level Algorithms
• Standard background on Discrete Probability

Research internships are available. Please contact the instructor.

• Analysis of random models for stable matchings. Simon Mauras, PhD thesis.
• Fairness of linear regression in decision making. Vincent Cohen-Addad, Surya Teja Gavva, C.S. Karthik, Claire Mathieu, Nanrata.
• A scheduling model for reduced CPU energy. Frances Yao, Alan Demers, Scott Shenker.
• Cake cutting. Suresh Venkatasubramanian.
• An envy-free Cake Division Protocol. Steven Brams and Alan Taylor.
• The Theory of Apportionment. M.L. Balinski and H.P. Young. Sections 2,3, beginning of 6.
• Balanced power diagrams for redistricting. Vincent Cohen-Addad, Philip Klein, Neal Young.
• Perspectives pour une évolution du programme de don croisé de reins en France. Julien Combe, Victor Hiller, Olivier Tercieux, et al.
• Long Paths in random graphs. Lecture notes. (M. Krivelevich?).

The following is a coherent list of courses on the thematic 'Algorithms and Complexity'.

• 2-11-1 Advanced Algorithms
• 2-11-2 Randomness in Complexity
• 2-12-1 Techniques in Cryptography and Cryptanalysis
• 2-13-2 Error correcting codes and applications to cryptography
• 2-18-1 Distributed algorithms for the networks
• 2-18-2 Algorithmique distribuée avec mémoire partagée
• 2-24-1 Optimisation
• 2-29-1 Graph algorithms
• 2-33-1 Theory of Computations
• 2-34-1 Quantum information and applications
• 2-38-1 Algorithms and combinatorics for geometric graphs

Main topics

• Continuous Methods in Combinatorial Optimization

Instructor

• Adrian Vladu (IRIF)

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.

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.

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.

• Graphs, Linear Algebra, and Optimization, lecture notes by Aleksander Madry,https://people.csail.mit.edu/madry/6S978/
• Spectral Algorithms, lecture notes by Richard Peng, https://faculty.cc.gatech.edu/~rpeng/CS7540_S17/
• Techniques in Optimization and Sampling, by Yin Tat Lee and Santosh Vempala, https://www.dropbox.com/s/10zwtzolc1qhpsq/main.pdf
• Laplacian Solvers and Their Algorithmic Applications, by Nisheeth Vishnoi, https://theory.epfl.ch/vishnoi/Lxb-Web.pdf