Objectifs :
4 lectures

Programme :
In this doctoral course we will introduce expander graphs, which are sparse graphs with a pseudorandom behaviour. They have been at the heart of major breakthroughs in discrete mathematics and theoretical computer sciences over the past 30 years. We will mainly focus on their applications in theoretical computer science.

We will cover the following:
-Expansion and spectral expansion
-Error reduction for randomized algorithms
-The construction of expander graphs (with application to st-connectivity in logarithmic space)
-Error correcting codes
(and if time permits:
-Hardness of approximation and the PCP theorem
-Expander graph decompositions and their algorithmic applications
-Applications of expander graphs in geometry)

Pré-requis :
Prerequisite: basics of graph theory and linear algebra

Equipe pédagogique :
Louis Esperet

Les Compétences et capacités visées à l'issue de la formation (fiches RNCP)

Arrêté du 22 février 2019 définissant les compétences des diplômés du doctorat et inscrivant le doctorat au répertoire national de la certification professionnelle. https://www.legifrance.gouv.fr/loda/id/JORFTEXT000038200990/

Bloc 1 : Concevoir et élaborer une démarche de recherche, de R&D ou d'innovation

- Disposer d'une expertise scientifique tant générale que spécifique d'un domaine de recherche et de travail déterminé

- Faire le point sur l'état et les limites des savoirs et des pratiques au sein d'un secteur d'activité déterminé, aux échelles locale, nationale ou internationale

- Identifier les problématiques pour résoudre les problèmes complexes et nouveaux impliquant une pluralité de domaines en mobilisant et en produisant les connaissances et savoir-faire les plus avancés

- Identifier les possibilités de ruptures conceptuelles et concevoir le cas échéant des axes d'innovation pour un secteur professionnel

Bloc 2 : Mettre en œuvre une démarche de recherche, de R&D ou d'innovation

- Apporter des contributions novatrices dans le cadre d'échanges de haut niveau, et dans des contextes internationaux

- Mettre en œuvre les méthodes et les outils de la recherche, le cas échéant en lien avec l'innovation

- Mettre en œuvre les principes, outils et démarches d'évaluation des coûts et de financement d'une démarche d'innovation ou de R&D

Bloc 4 : Assurer une veille scientifique et technologique de haut niveau à l’échelle internationale

- Acquérir, synthétiser et analyser les données et les informations scientifiques et technologiques d’avant- garde à l’échelle internationale en développant un regard critique et distancié

- Dépasser les frontières des données et du savoir disponibles par croisement avec différents champs de la connaissance ou d'autres secteurs professionnels

La formation participe à l'objectif suivant :conforter la culture scientifique des doctorants dans leur champ disciplinaire ou en interdisciplinaire