Séminaire

Équipe thématique Algorithmes et complexité
Équipe thématique Combinatoire
Équipe-projet INRIA GANG
Équipe thématique Systèmes complexes, réseaux, calcul distribué
Équipe thématique Théorie et algorithmique des graphes

Le calendrier des séances (format iCal).
Pour ajouter le calendrier des séances à votre agenda favori, souscrire au calendrier en indiquant ce lien.


Contact(s)


Séances passées



Année 2019

Algorithmes et structures discrètes
Mercredi 2 octobre 2019, 11 heures, Salle 3052
Sophie Laplante (IRIF) The sensitivity conjecture and a recent proof of it (part II)

Informal presentation.

Algorithmes et structures discrètes
Jeudi 26 septembre 2019, 14 heures, Salle 3052
Sophie Laplante (IRIF) The sensitivity conjecture and a recent proof of it (part I)

Informal presentation.

Algorithmes et structures discrètes
Lundi 24 juin 2019, 11 heures, Salle 3052
Carola Doerr (CNRS, LIP6) Evolutionary Algorithms – From Theory to Practice and Back

Most real-world optimization problems do not have an explicit problem formulation, but only allow to compute the quality of selected solution candidates. Solving such black-box optimization problems requires iterative procedures which use the feedback gained from previous evaluations to determine the strategy by which the next solution candidates are generated. Many black-box optimization algorithms, such as Simulated Annealing, Evolutionary Algorithms, Swarm Intelligence Algorithms, are randomized – making it very difficult to analyze their performances mathematically. In the last 15 years, the theory of randomized black-box optimization has advanced considerably, and has contributed to efficient optimization by providing insights into the working principles of black-box optimization which are hard or impossible to obtain by empirical means. On the other hand, empirically-guided benchmarking has opened up new research directions for theoretical investigations. In this presentation we will discuss the state of the art in the theory of randomized black-box optimization algorithms. As part of this critical survey we will also mention a number of open questions and connections to other fields of Computer Science.

Algorithmes et structures discrètes
Jeudi 9 mai 2019, 15 heures, Salle 1007
Amélie Gheerbrant (IRIF) Graph query languages

Graph databases use graph structure to represent and query data. The talk will survey some graph query languages used in this context, with a focus on regular path queries (RPQs) and conjunctive regular path queries (CRPQs). We will present the different semantics that graph database systems use for them (every path, simple path, trail), and recall computational complexities of query evaluation and query containment. We will finally discuss some issues related to querying not only the topology but also the data of the graph and present a few open problems that could be of interest both to the graph and algorithms group and to the automata group.

Algorithmes et structures discrètes
Mardi 19 février 2019, 11 heures, Salle 3052
Danupon Nanongkai (KTH) Distributed Shortest Paths, Exactly

This talk concerns the problem of quickly computing distances and shortest paths on distributed networks (the CONGEST model). There have been many developments for this problem in the last few year, resulting in tight approximation schemes. This left open whether exact algorithms can perform equally well. In this talk, we will discuss some recent progress in answering this question. Most recent works that this talk is based on are with Sebastian Krinninger (FOCS 2018) and Aaron Bernstein (ArXiv 2018).


Année 2018

Algorithmes et structures discrètes
Lundi 3 décembre 2018, 11 heures, Salle 3052
Cédric Boutillier (LPSM, Sorbonne Université) Statistical mechanics on isoradial graphs

Isoradial graphs are embedded planar graphs in such a way that every face is inscribed in a circle of radius 1. They are a perfect ground to develop a theory of discrete complex analysis and to define integrable models in statistical mechanics. In this talk, we will describe combinatorial and geometric aspects of these graphs, and their impact on locality of some models of statistical mechanics (dimer models, random walk, spanning trees…)