Équipe thématique Algorithmes et complexité

Équipe thématique Combinatoire

Équipe-projet INRIA (La référence de gang est supprimée le 20/01/2021) GANG

Équipe thématique Théorie et algorithmique des graphes

## Algorithmes et structures discrètes

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 2020

Algorithmes et structures discrètes

Mardi 26 mai 2020, 11 heures, Online

**Édouard Bonnet** (ENS Lyon) *Twin-width*

Joint work with Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant

Algorithmes et structures discrètes

Lundi 27 janvier 2020, 9 heures 30, 3052

**Amaury Pouly** (IRIF) *Continuous models of computation: computability, complexity, universality*

A few years ago, it was shown that Turing-based paradigms and the GPAC have the same computational power. However, this result did not shed any light on what happens at a computational complexity level. In other words, analog computers do not make a difference about what can be computed; but maybe they could compute faster than a digital computer. A fundamental difficulty of continuous-time model is to define a proper notion of complexity. Indeed, a troubling problem is that many models exhibit the so-called Zeno's phenomenon, also known as space-time contraction.

In this talk, I will present results from my thesis that give several fundamental contributions to these questions. We show that the GPAC has the same computational power as the Turing machine, at the complexity level. We also provide as a side effect a purely analog, machine- independent characterization of P and Computable Analysis.

I will present some recent work on the universality of polynomial differential equations. We show that when we impose no restrictions at all on the system, it is possible to build a fixed equation that is universal in the sense it can approximate arbitrarily well any continuous curve over R, simply by changing the initial condition of the system.

If time allows, I will also mention some recent application of this work to show that chemical reaction networks are strongly Turing complete with the differential semantics.

Algorithmes et structures discrètes

Jeudi 23 janvier 2020, 11 heures, Salle 1007

**Moni Naor** (Weizmann Institute) *Instance Complexity and Unlabeled Certificates in the Decision Tree Model*

In this talk I will discuss labeled and unlabeled certificates, in particular in the context of ``instance optimality“. This is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, respectively.

Joint work with Tomer Grossman and Ilan Komargodski

#### 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)*

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)*

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*

Algorithmes et structures discrètes

Jeudi 9 mai 2019, 15 heures, Salle 1007

**Amélie Gheerbrant** (IRIF) *Graph query languages*

Algorithmes et structures discrètes

Mardi 19 février 2019, 11 heures, Salle 3052

**Danupon Nanongkai** (KTH) *Distributed Shortest Paths, Exactly*

#### 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*