The calendar of events (iCal format).
In order to add the event calendar to your favorite agenda, subscribe to the calendar by given this link


Previous talks

Year 2019

Algorithms and discrete structures
Wednesday October 2, 2019, 11AM, Salle 3052
Sophie Laplante (IRIF) The sensitivity conjecture and a recent proof of it (part II)

Informal presentation.

Algorithms and discrete structures
Thursday September 26, 2019, 2PM, Salle 3052
Sophie Laplante (IRIF) The sensitivity conjecture and a recent proof of it (part I)

Informal presentation.

Algorithms and discrete structures
Monday June 24, 2019, 11AM, 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.

Algorithms and discrete structures
Thursday May 9, 2019, 3PM, 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.

Algorithms and discrete structures
Tuesday February 19, 2019, 11AM, 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).

Year 2018

Algorithms and discrete structures
Monday December 3, 2018, 11AM, 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…)