Winter School / I.H.P. graduate program

Combinatorial and algorithmic aspects of convexity

Paris, Institut Henri Poincaré (I.H.P.), January 19-23, 2015


This Winter School will consist in two courses of 10 hours each, given by professors I. Bárány and S. Vempala:

Imre Bárány
(Rényi Institute of Math., Hungarian Academy of Sciences, UCL)
Combinatorial properties of convex sets.
The course will cover several topics in combinatorial convexity, where theorems of Caratheodory, Helly, Radon, and Tverberg are the typical and classical results. We plan to investigate weak epsilons-nets, halving lines and planes, the $(p,q)$ problem and its solution, extensions to lattice convex sets, and colourful versions of the above mentioned classical theorems. Further possible topics are transversals, lattice polytopes and random polytopes. The methods here use tools from linear algebra, combinatorics, topology, geometry, probability theory, and geometry of numbers.
Notes of all lectures. Notes of lecture 1, lecture 2, lecture 3, lecture 4 and lecture 5.
Santosh Vempala
(Georgia Tech.)
Algorithmic aspects of convexity.
Convexity plays an important role in algorithmic complexity theory. Fundamental problems that are intractable in general become polynomial-time solvable with a suitable convexity assumption. We will discuss this phenomenon for optimization, integration, sampling and learning. The resulting algorithms are based on a range of tools, including the analysis of Markov chains, geometric isoperimetric inequalities, concentration of measure, rounding via affine transformations and simulated annealing. The course will begin with some motivating algorithms, then present relevant properties of convex sets and their extensions to log-concave functions, continue with sampling algorithms and conclude with applications of high-dimensional sampling.

Notes of all lectures. Notes of lecture 1, lecture 2, lecture 3, lecture 4 and lecture 5.

The courses are part of the A.N.R. project GeMeCoD, the Graduate program of the I.H.P. and the École Doctorale MSTIC de l'Université Paris-Est and are addressed to non-specialists. Participation of postdocs and PhD students is strongly encouraged.

Imre Bárány courses are part of his invitation on the Bézout chair awarded by the Bézout Labex.


Lectures are held in some of the amphitheaters of the campus Curie, from Monday, January 19 to Friday, January 23.
Coffee will be served in the cafeteria of IHP, situated in the lobby, on the ground floor of IHP.
Lunch: There are plenty of restaurants all around the IHP (see the map) and weather permitting, it is also possible and very nice to buy a sandwich and bring it to the Luxembourg garden.

Day Monday 19 Tuesday 20 Wednesday 21 Thursday 22 Friday 23
Amphitheater Chaudron (ENSCP) Chaudron (ENSCP) Darboux (IHP) Darboux (IHP) Darboux (IHP)
9:15-9:45 Registration/Coffee Coffee Coffee Coffee Coffee
9:50-12:00 Bárány Bárány Bárány Bárány Bárány
12:00-13:15 Lunch Lunch Lunch Lunch Lunch
13:15:13:45 Coffee Coffee Coffee Coffee
13:45-16:00 Vempala Vempala Vempala Vempala Vempala
16:15-16:45 Coffee Brazitikos: KLS conjecture part I Lelarge: Polytope phase transition Sarrabezolles: colorful linear programming Coffee
16:45-17:15 Cousins: KLS conjecture part II Ambrus: Extremal vector systems Hubard: limits of order types
17:15-17:45 Grupel: KLS conjecture part II

Short talks

We have added a few short talks in the afternoon of Tuesday, Wednesday and Thursday as one can see in the above schedule.

Tuesday Three talks on KLS conjecture by

Silouanos Brazitikos (University of Athens),
Ben Cousins (Georgia Institute of Technology)
Uri Grupel (Tel-Aviv University).


Marc Lelarge (INRIA-ENS): Universality in polytope phase transition and message passing algorithms
Gergely Ambrus (Université Paul Sabatier Toulouse): Extremal vector systems.


Pauline Sarrabezolles (Ecole des Ponts): Colorful linear programing
Alfredo Hubard (INRIA/UPEM): limits of order types.

Practical informations

Be sure to book your hotel very early (at least a month in advance), since accommodations in Paris are difficult to find.


Matthieu Fradelizi (LAMA, UPEM), Xavier Goaoc (LIGM, UPEM), Nathaël Gozlan (LAMA, UPEM), Nabil Mustafa (LIGM, ESIEE), Paul-Marie Samson (LAMA, UPEM)


Participants / Registration

Registration is closed.

Organizers Affiliation
Fradelizi, Matthieu Université Paris-Est Marne-la-Vallée
Goaoc, Xavier Université Paris-Est Marne-la-Vallée
Gozlan, Nathael Université Paris-Est Marne-la-Vallée
Mustafa, Nabil Universite Paris-Est ESIEE Paris
Samson, Paul-Marie Université Paris-Est Marne-la-Vallée
Participants Affiliation
Samadi, Samira University of British Columbia
Cousins, Ben Georgia Institute of Technology
Ambrus, Gergely Toulouse
Memarian, Yashar None
Chretien, Stephane Laboratoire de Mathématiques, Université de Franche Comté
Rotem, Liran Tel-Aviv University
Ergur, Alperen Ali Texas A&M University
Silverstein, Laura Vienna University of Technology
Brazitikos, Silouanos University of Athens
Chasapis, Giorgos University of Athens
Draief, Moez Imperial College London
Haase, Christoph LSV - CNRS & ENS Cachan
Nguyen, Kim Thang IBISC, Université Evry
Broutin, Nicolas Inria
Tsigaridas, Elias Inria
Stavrakakis, Pantelis University of Athens
Nicaud, Cyril LIGM, Université Paris-Est Marne-la-Vallée
Fisikopoulos, Vissarion Université libre de Bruxelles
Basu Roy, Aniket Indian Institute of Science, Bangalore
Alipour, Sharareh Sharif University of Technology
Barba, Luis Carleton University/Université Libre de Bruxelles
Riener, Cordian Aalto University Helsinki
Fang, Lincong University of Burgundy
Grupel, Uri Tel-Aviv University
Jesús, Rebollo Bueno University of Seville
Lelarge, Marc INRIA-ENS
Yun, Seyoung MSR-Inria
Anderson, Joe The Ohio State University
Dirksen, Hauke Kiel University
Ducoffe, Guillaume INRIA/I3S - Equipe COATI
Roy, Aurko Georgia Institute of Technology
Abhinav Jauhri, Abhinav Carnegie Mellon University
Basak, Aniruddha Carnegie Mellon University
Nguyen, Van Hoang Tel Aviv University
Mailler, Cécile University of Bath
Manneville, Thibault Laboratoire d'informatique de Polytechnique (LIX)
González Merino, Bernardo University of Murcia
Ashok, Pradeesha Institute of Mathematical Sciences, India
Kim, Heuna Freie Universität Berlin
Bonnet, Gilles University of Osnabrueck
Khandwawala, Mustafa INRIA
Blanco, Mónica University of Cantabria, Spain
Psarros, Ioannis University of Athens
Samaras, Georgios University of Athens
Singh, Karan Indian Institute of Technology, Kanpur
Hioni, Labrini University of Athens
Afuwape , Oluwaseun Bamtex properties Nigeria limited
Pocchiola, Michel Institut de Mathématiques de Jussieu-PRG
Friedland, Omer Paris 6
Attia, Mohamed Jalel University of Gabès, Tunisia
Colin de Verdière, Éric École normale supérieure (Paris), CNRS
shabbir, mudassir Rutgers University
Tkocz, Tomasz University of Warwick
Alonso Gutiérrez, David Universitat Jaume I
Hubard, Alfredo INRIA/Université Paris-Est Marne-la-Vallée
Chevillard, Sylvain INRIA
Bureaux, Julien Paris 10
Martínez Sandoval, Leonardo Ignacio Instituto de Matemáticas UNAM
Reisner, Shlomo University of Haifa
Strzelecki, Michał University of Warsaw
Strzelecka, Marta University of Warsaw
Luviano-Flores, Johana Department of Mathematics-CINVESTAV
Barthe, Franck Université de Toulouse
Tkadlec, Josef IST Austria
Anagnostopoulos, Evangelos University of Athens
zouhaier, raddaoui University of Gabès, Tunisia
Yepes Nicolás, Jesús University of Murcia
Dann, Susanna Vienna Institute of Technology
Huszár, Kristóf IST Austria
de Mesmay, Arnaud IST Austria
Leonardos, Nikos LIAFA
de Castro, Yohann Université Paris Sud
Bohn, Adam Université Libre de Bruxelles
glisse, marc inria
Kopecka, Eva University of Innsbruck
Livne Bar-on, Amir Tel-Aviv University
Cordero-Erausquin, Dario Paris 6
van Duijn, Ingo Aarhus University
Rav, Mathias Aarhus University
Abdelkader, Ahmed University of Maryland
Mordhorst, Olaf Christian-Albrechts-Universität zu Kiel
de Laat, David TU Delft
Prochno, Joscha Johannes Kepler University
Meunier, Frédéric Ecole des Ponts
Sarrabezolles, Pauline Ecole des ponts
Freij, Ragnar Aalto University
Berg, Soeren TU Berlin
Pollehn, Hannes TU Berlin
Faifman, Dmitry IHES
Dai, Liang Uppsala University
Stein, Yannik Freie Universität Berlin
Kleinschmidt, Colin Christian-Albrechts-Universität zu Kiel
Lee, Seunghun KAIST
de Joannis de Verclos, Rémi Laboratoire G-SCOP (Grenoble-INP, CNRS), Grenoble, France.
Segal, Alexander Tel Aviv University
De Vitis, Alba Chiara INRIA
Naszodi, Marton EPFL, Lausanne
Reichenwallner, Benjamin University of Salzburg
Saffar, Ilhem Université Paris Descartes
Kanade, Varun École normale supérieure
Bardet, Jean-Baptiste Université de Rouen
leconte, mathieu Huawei
Tomasi, Beatrice Mathematical and Algorithmic Sciences Lab, France Research Center, Huawei Technologies Co. Ltd.
Abdullah, Mohammed Mathematical and Algorithmic Sciences Lab, Huawei France
Pajor, Alain Université Paris-Est Marne-la-Vallée
Bus, Norbert Universite Paris Est
Bonis, Thomas inria
Huang, Ruqi INRIA
Ren, Iris Yuping Ecole Polytechnique
Guédon, Olivier Université Paris-Est Marne-la-Vallée
Nemparis, Ioannis University of Athens
manoussakis, george université paris sud
Castelli Aleardi, Luca LIX, Ecole Polytechnique
SUN, Qiang LRI, Université Paris-Sud
XU, Renyu LRI
Benyó, Krisztián Université Paris-Est, Marne-la-Vallée
Langerman, Stefan Université Libre de Bruxelles
Mattei, Pierre-Alexandre MAP5, université Paris Descartes
Nolin, Alexandre Ecole Polytechnique, Université Paris Diderot
pisier, gilles paris 6
Conceicao, Pedro Vitor iHP/University of brasilia

Supported by

winterschool2015.txt · Last modified: 2015/07/03 08:53 by FRADELIZI Matthieu
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki