Thematic team Algorithms and complexity

Thematic team Combinatorics

Thematic team Complex systems, networks, and distributed computing

INRIA project-team 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 given this link

#### Contact(s)

### Next talk

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

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

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*