Thematic team Algorithms and complexity

Thematic team Combinatorics

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

Thematic team Theory and algorithmics of graphs

## Algorithms and discrete structures

The calendar of events (iCal format).

In order to add the event calendar to your favorite agenda, subscribe to the calendar by using this link.

#### Contact(s)

### Previous talks

#### Year 2021

Algorithms and discrete structures

Tuesday June 15, 2021, 2PM, 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

#### Year 2020

Algorithms and discrete structures

Tuesday May 26, 2020, 11AM, Online

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

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

Algorithms and discrete structures

Monday January 27, 2020, 9:30AM, 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.

Algorithms and discrete structures

Thursday January 23, 2020, 11AM, 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

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

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

Algorithms and discrete structures

Monday June 24, 2019, 11AM, Salle 3052

**Carola Doerr** (CNRS, LIP6) *Evolutionary Algorithms – From Theory to Practice and Back*

Algorithms and discrete structures

Thursday May 9, 2019, 3PM, Salle 1007

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

Algorithms and discrete structures

Tuesday February 19, 2019, 11AM, Salle 3052

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

#### Year 2018

Algorithms and discrete structures

Monday December 3, 2018, 11AM, Salle 3052

**Cédric Boutillier** (LPSM, Sorbonne Université) *Statistical mechanics on isoradial graphs*