Fiches de cours 2017-2018

PDF
 

Analytic algorithms

CS-435

Enseignant(s) :

Vishnoi Nisheeth

Langue:

English

Summary

In the last decade, many fundamental algorithmic problems have benefited from viewing the underlying discrete problems through the lens of continuous/analytic methods. In this course we will introduce a selection of such techniques and explore their applications.

Content

' Convexity and gradient descent

' Multiplicative weight update (MWU) method and online convex optimization

' Gradient descent based methods for solving linear equations

' Optimization problems involving polynomials

' Graphs and their eigenvectors and eigenvalues

' Graphs as electrical networks 

' Graphs Laplacians and solving Laplacian equations

' Application: Fast algorithms to compute network flows (using  MWU, electrical flows and Laplacian solvers)

' Application: Fast algorithms for graph cuts (using eigenvectors and Laplacian solvers)

' Application: Algorithms for counting perfect matchings in graphs (using convex programs involving polynomials)

 

Keywords

Convex optimization, Spectral methods, Polynomials, Discrete Optimization, Continuous Optimization

Learning Prerequisites

Required courses

Calculus (MATH105), Linear Algebra (MATH110), Algorithms (CS250), Theory of Computation (CS251) or equivalents, Advanced Algorithms (CS-450) (or equivalent).

 

Recommended courses

 

 

Important concepts to start the course

This is an advanced course and requires mathematical maturity including linear algebra, multi-variate calculus, analysis, probability and algorithms.

Learning Outcomes

By the end of the course, the student must be able to:

Assessment methods

Homeworks, Scribe Notes, Exam and Project/Presentation*.

*Tentative

Resources

Bibliography

Books relevant to the course:

Vishnoi - Lx=b

Nesterov - Introductory lectures on convex optimization

Shalev-Schwartz - Online learning and online convex optimization

References for Basics:

Apostol - Calculus I and II

Strang - Linear algebra and its applications

Boyd and Vanderberghe - Convex optimization

Strogatz - Nonlinear dynamics and Chaos

Ressources en bibliothèque
Notes/Handbook

Vishnoi - Zeros of Polynomials and their Applications to theory. Available from http://theory.epfl.ch/vishnoi/Publications_files/ZerosIntro.pdf

 

Vishnoi -- A mini-course on convex optimization. Available from http://theory.epfl.ch/vishnoi/Nisheeth-VishnoiFall2014-ConvexOptimization.pdf

 

Dans les plans d'études

Semaine de référence

 LuMaMeJeVe
8-9     
9-10     
10-11     
11-12     
12-13     
13-14     
14-15     
15-16     
16-17     
17-18     
18-19     
19-20     
20-21     
21-22     
En construction
 
      Cours
      Exercice, TP
      Projet, autre

légende

  • Semestre d'automne
  • Session d'hiver
  • Semestre de printemps
  • Session d'été
  • Cours en français
  • Cours en anglais
  • Cours en allemand