É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 2021

Algorithmes et structures discrètes

Mardi 15 juin 2021, 14 heures, Salle 3052

**Magnús Halldórsson** (Reykjavik University) *New Vistas in Distributed Graph Coloring*

We present a new approach for randomized distributed Delta+1-coloring that is dramatically simpler than the previous best: the seminal work of Chang, Li, and Pettie (CLP) in SICOMP 2020. This approach offers numerous refinements: It matches the O(log^3 log n) round complexity in general, while on high-degree graphs (Delta » log^2 n), it uses only O(log* n) rounds. It uses small messages, i.e., works also in the CONGEST model. It also offers tradeoffs between the number of colors used, the round complexity, and the clique number of the graph.

We expect that the approach presented will lead the way towards improved results for various coloring problems in the near future.

This is based on a paper at STOC'21, joint work with Fabian Kuhn, Yannic Maus, and Tigran Tonoyan; and a more recent one on arXiv, joint with Alexandre Nolin, and Tigran Tonoyan.

The seminar will be available online by the following ZOOM-link:

https://u-paris.zoom.us/j/84049775680?pwd=Yk5lMDhlZUNQRGMyelExMVdoM2poQT09

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