Basic courses in analysis, algebra, probability and geometry.

Basic courses in complexity, algorithmic, programming and graphs

Discrete optimization : Min-max results in combinatorial optimization provide elegant mathematical statements, are often related to the existence of efficient algorithms, and illustrate well the power of duality in optimization. The course will rely on concrete examples taken from industry. Plan of the course: Discrete optimization in bipartite graphs. Chains and antichains in posets. Chordal graphs. Perfect graphs. Lovász theta function. Continuous optimization : The course will cover over theoretic and algorithmic aspects of convex  optimization in a finite-dimensional setting. Plan of the course: Linear programming, the simplex algorithm, totally unimodular matrices, convex fuctions, semi-definite programming, convex programming, Karush-Kuhn-Tucker conditions. Weak and strong duality, Farkas Lemma. Sparse solutions via L1 penalization. LASSO method.

Probabilistic algorithms. This course is about randomized algorithms, which relies on randomness to speed up their running time. The methods: Las Vegas and Monte Carlo algorithmes, complexity classes for randomized algorithms, lower bounds: Yao’s Minimax principle, some probabilistic settings useful in algorithms: coupon collector, birthday problem, …Applications: analysis of Quicksort and Quickselect algorithms, stable marriage problem, probabilistic data structures (hash tables, skip lists, treaps, …), probabilistic counting, graph algorithms. Combinatorics. The lectures on enumerative combinatorics will consist in the study of classical objects: permutations, trees, partitions, parking functions, …- classical sequences: factorial, Catalan, Schroder, …- classical methods: bijections, group actions, induction, generating series.The lectures will be heavily based on the study of various examples, some very easy and others trickier.

Discrete differential geometry. Extension of curvature to discrete objects such that polyedra or graphs. Geometric flow under constraint preserves a texture mapping along deformation. Programm : Discrete surface theory, topology and Gaussian curvature, Gauss Bonnet theorem. Discrete differential calculus. Discrete mean curvature on triangulated surfaces. Parametrization by line of curvature, Quadrangulation and application to architecture. Intrinsic curvature and application to graph theory. Discrete isoperimetry. We extend the classical isoperimetric problem (which sets have maximal area among sets of given perimeter) to graphs. We present : Brunn-Minkowski and Loomis-Whitney theorems, entropy, Sauer-Shelah, Harper’s theorems, Boolean analysis on the hypercube, Cheeger’s theorem linking the spectral gap to expansion properties of a graph and we give algebraic and probabilistic constructions of families of expander graphs.

Machine learning. OBJECTIVES: Understanding  of the principal Artificial Intelligence algorithms: machine & deep learning. Introduction to the optimization and the stochastic approximation algorithms for learning. Building predictive methods on unstructured datasets such as text data. PROGRAM: Introduction to statistical learning: theoretical and empirical risk, Bias-Variance equilibrium, overfitting; Aggregating methods: random forests; bagging and boosting methods; Kernels methods and Support Vector machine algorithms; Convexification, regularization and penalization technics: Lasso, Ridge, elastic net.. ; Deep learning algorithms: feedforward, convolutional and recurrent networks, dropout regularization; Prediction with unstructured text data:  bagofwords, word2vec; Introduction to reinforcement learning.

The objective is to present the theory of large dense graphs, in their analytical, probabilistic and combinatorics aspects. Program : introduction and reminders on finite graphs ; definition of a graphon, graphon as a generator of dense random graphs ; properties of the space of graphons, cut-distance ; convergence of large graphs to a graphon ; sampled graphs; Inequalities of concentration and convergence ; application: classical combinatorial inequalities ; application: epidemic on a graphon, graphs biased by size ; application: degree function, exponential model

Operads in combinatorics: Informally, an operad is a space of operations having one output and several inputs that can be composed. We present some elementary objects of algebraic combinatorics: combinatorial classes and algebras. We introduce (non-symmetric) operads and study some tools allowing to establish presentations by generators and relations of operads. Koszul duality and generalizations: colored operads, symmetric operads, and pros. We shall also explain how the theory of operads offers a tool to obtain enumerative results. Algebraic combinatorics : study of classical symmetric functions and discussion about representation theory, noncommutative symmetric functions (NCSF), the definition of Hopf algebras, the dual algebra of NCSF, quasi-symmetric functions, the modern generalizations of those algebras and use of all these algebraic properties (transition matrices, expressions in various bases, morphisms of Hopf algebras) to solve (classical) combinatorial questions.

The purpose of large Random Matrix Theory (RMT) is to describe the eigenstructure (eigenvectors and eigenvalues) of matrices whose entries are random variables and whose dimensions go to infinity. The first results go back to Wigner (1948) for random symmetric matrices and Marchenko and Pastur (1967) for large covariance matrices. Both results have been motivated by questions in theoretical physics which still provides open problems. In the eighties, Voiculescu used RMT as a tool to address open problems in operator theory. This point of view turned to be extremely successful as many such open problems received a solution with the help of RMT. A whole theory known as free probability has been developed which tightly relies on RMT. In the nineties, RMT turned to be very successful to address problems in wireless communications, to analyze the performances of multi-antenna telecommunication networks, and to provide usefull results in statistical signal processing. For 20 years, the theory of large random matrices is very active as can be seen by the publication of five major monographs on the subject. The goal of the course is to present the most classical and prominent results in the field together with some statistical applications: Basic techniques in RMT and Stieltjes transform; Marchenko-Pastur’s theorem which describes the limiting spectral measure of large covariance matrices; other models of interest: large covariance matrices with general population matrix, signal + noise matrices, etc.; Small perturbations and spiked models. In terms of applications, we will describe the problem of statistical test in large dimension and other statistical problems.