M2 Informatique fondamentale 2017-2018
Discrete mathematics course
Focus: isoperimetry and approximation algorithms

Instructors. Matthieu Fradelizi (matthieu.fradelizi@u-pem.fr), Xavier Goaoc (goaoc@univ-mlv.fr) and Alfredo Hubard (Alfredo.Hubard@u-pem.fr).

Topic. This course will explore various aspects of isoperimetry in discrete mathematics and several of its applications, in particular in algorithms.

Location. The lectures will take place at Université Paris Est Marne-la-Vallée, Copernic building (RER stop Noisy-Champs), 4th floor. Directions can be found here.

Schedule.

• Week 1
  • Fri, jan 26th, 10:45-12:45, room 4B09R (Hubard) The volume computation problem: hardness and approximation via sampling
  
  
• Week 2
  • Thu, feb 1st, 10:45-12:45, room 4B09R (Fradelizi) Brunn-Minkowski, concentration, flattening lemma, application to nearest neighbor computation
    Complementary reading: Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions, by Andoni and Indyk. See also this page.
  • Fri, feb 2nd, 10:45-12:45, room 4B09R (Goaoc) Loomis-Whitney inequality, Sauer's lemma, epsilon-net theorem and some of its applications
  • Distribution of homework 1
  
  
• Week 3 (5-9 feb)
  • Thu, feb 8th, 10:45-12:45, room 4B09R (Goaoc) epsilon-net theorem and combinatorial isoperimetry: theorems of Harper and Kruskal-Katona
  • Fri, feb 9th, 10:45-12:45, room 4B09R (Fradelizi) Thresholds in random graphs: small graphs and connectivity
  
  
• Articles proposed for the final presentations
  
  
  1. An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in Gauss space by Bobkov
  2. Concentration of the distance in finite dimensional normed spaces by Arias-de-Reyna, Ball and Villa
  3. Excluded permutation matrices and the Stanley-Wilff conjecture by Marcus and Tardos
  4. The traveling salesman problem in bounded degree graphs by Bjorklund, Husfeldt, Kaski and Koivisto
  5. Nonembeddability theorems via Fourier analysis (section 1 to 3) by Khot and Naor
  6. The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomials by Kane
  7. Shallow excluded minors and improved graph decompositions, by Plotkin, Rao and Smith
  8. Economical toric spines via Cheeger's inequality by Alon and Klartag
  9. An elementary construction of constant-degree expanders by Alon, Schwartz and Shapira
  
  
• Week 4 (12-16 feb)
  • Thu, feb 15th, 10:45-12:45, room 4B09R (Hubard) Poincare inequality and property testing
  • Fri, feb 16th, 10:45-12:45, room 4B09R (Fradelizi) Thresholds by boolean analysis
  • Reading assignment for the final presentations
  
  
• One-week break
  
  
• Week 5 (26 feb-2 mar)
  • Thu, mar 1st, 10:45-12:45, room 4B09R (Goaoc) Introduction to spectral graph theory
  • Fri, mar 2nd, 10:45-12:45, room 4B09R (Hubard) Expander graphs, Cheeger inequality and its algorithmic applications
  • Homework 1 due
  • Distribution of homework 2
  
  
• Week 6 (5-9 mar)
  • Thu, mar 8th, 10:45-12:45, room 4B09R (Fradelizi) Planar graphs and circle packing
  • Fri, mar 9th, 10:45-12:45, room 4B09R (Goaoc) Planar separator theorem and some of its algorithmic applications
  
  
• Week 7 (12-16 mar)
  • Thu, mar 15th, 10:45-12:45, Algéco C02 (Hubard) Construction of expander graphs 1/2
  • Fri, mar 16th, 10:45-12:45, Algéco C08 (Fradelizi) Construction of expander graphs 2/2
  
  
• Week 8 (19-23 mar)
  • Thu, mar 22nd, 10:45-12:45, Algéco B03 (Hubard) Some applications of expander graphs
  • Fri, mar 23rd, 10:45-12:45, Algéco C02 (Goaoc) What was it all about?
  • Homework 2 due
  • Presentations of reading assignments