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

Main topics

• Continuous Methods in Combinatorial Optimization

Instructors

• 2022-2023: Adrian Vladu (IRIF)
• 2023-2024: Claire Mathieu (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.

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

Research internships are available. Please contact the instructor.

• 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

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