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 : Conception et élaboration d’une démarche de recherche et développement, d’études et prospective

- 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 au sein d’un secteur d’activité déterminé, aux échelles locale, nationale ou internationale

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

- Identifier les possibilités de ruptures conceptuelles et concevoir des axes d’innovation pour un secteur professionnel

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

- S’adapter en permanence aux nécessités de recherche et d’innovation au sein d’un secteur professionnel

Bloc 2 : Mise en œuvre d’une démarche de recherche et développement, d’études et prospective

- Mettre en œuvre les méthodes et les outils de la recherche 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 : Veille scientifique et technologique à l’échelle internationale

- Acquérir, synthétiser et analyser les données et informations scientifiques et technologiques d’avant-garde à l’échelle internationale

- Disposer d’une compréhension, d’un recul et d’un regard critique sur l’ensemble des informations de pointe disponibles

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

- Disposer de la curiosité, de l’adaptabilité et de l’ouverture nécessaire pour se former et entretenir une culture générale de haut niveau

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