Équipe thématique Algorithmes et complexité

Équipe thématique Combinatoire

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

### Prochaine séance

Algorithmes et structures discrètes

Vendredi 13 septembre 2024, 14 heures, Salle 3052

**Shuichi Hirahara** (National Institute of Informatics, Japan) *Planted Clique Conjectures Are Equivalent*

Joint work with Nobutaka Shimizu. Paper: https://eccc.weizmann.ac.il/report/2024/058/

### Séances passées

#### Année 2024

Algorithmes et structures discrètes

Vendredi 14 juin 2024, 15 heures 30, Salle 3052

**Venkatesan Guruswami** (Simons Institute) *When and why do efficient algorithms exist (for constraint satisfaction and beyond)?*

Inspired and emboldened by this, one might speculate a polymorphic principle in more general contexts, with symmetries in the solution space governing efficient algorithms. Beginning with some background on CSP and the polymorphic approach to understanding their complexity, the talk will discuss some extensions beyond CSP where the polymorphic principle seems promising (yet far from understood). In particular, we will discuss “promise CSP” (PCSP) where one is allowed to satisfy a relaxed version of the constraints (a framework that includes important problems like approximate graph coloring). We will provide glimpses of the emerging polymorphic theory characterizing the (in)tractability of interesting classes of PCSP as well as the ability of natural classes of algorithms to solve them.

#### Année 2023

Algorithmes et structures discrètes

Mardi 18 avril 2023, 15 heures 30, 3052, Sophie Germain

**Mamadou Kanté** (LIMOS, Clermond-Ferrand) *Lettericity of graphs and griddability of permutations*

Algorithmes et structures discrètes

Mercredi 5 avril 2023, 15 heures, 3052

**Lélia Blin** (LIP6) *Self-Stabilizing Distributed Algorithms*

Algorithmes et structures discrètes

Mercredi 22 mars 2023, 15 heures, 3052

**Michail Lampis** (LAMSADE) *First Order Logic on Pathwidth Revisited Again*

In this talk we take a high-level view of this area of research and survey results that attempt to improve upon this performance by considering more restricted classes of inputs. This is known to be impossible, even if we restrict the input to graphs of treewidth 1 (trees) and only consider FO logic; or if we consider graphs of pathwidth 1 (caterpillars) and consider MSO logic. This would seem to indicate that Courcelle's theorem is “best possible”. Surprisingly, we discover that in the only remaining case which has so far been overlooked, namely FO logic on graphs of constant pathwidth, all known hardness results fail, because the problem becomes tractable with an elementary parameter dependence on the input formula. Our result generalizes previously known meta-theorems for the much more restricted parameter tree-depth.

Results based on a preprint available here: https://arxiv.org/abs/2210.09899

#### Année 2022

Algorithmes et structures discrètes

Mardi 11 octobre 2022, 9 heures 30, Amphi Turing

** Anual Meeting Of Pole Asd, Presentation From New Members** (IRIF) *
*

*
09:30-10:00 - Marie Albenque
*

10:00-10:30 - Sergio Rajsbaum

10:30-11:15
`Short introduction of new postdocs and Ph.D. students followed by General discussion and then coffee break`

11:15-11:45 - Monika Csikos

11:45-12:15 - Sophie Laplante

*
Journée du pôle Algorithmes et structures discrètes 2021
The first and possibly the most fundamental problem in distributed graph algorithmics is the vertex coloring problem. The nodes of a network are processes that communicate via the edges in synchronous rounds. The most basic problem is to color the network using Delta+1 colors in as few rounds a possible, where Delta is the maximum degree of the graph.
Inspired by an invariant defined on permutations by Guillemot and Marx [SODA '14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, $K_t$-free unit ball graphs, posets with antichains of bounded size, and proper subclasses of permutation graphs all have bounded twin-width. On all these classes we will see how to compute in polynomial time a sequence of d-contractions, witness that the twin-width is at most d. FO model checking, that is deciding if a given first-order formula $\phi$ evaluates to true on a given binary structure G on a domain D, happens to be FPT in $|\phi|$ on classes of bounded twin-width, provided the witness is given. More precisely, being given a d-contraction sequence for G, our algorithm runs in time $f(d,|\phi|) |D|$ where f is a computable but non-elementary function. We will also see that bounded twin-width is preserved by FO interpretations and transductions. This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarsky et al. [FOCS '15]. Finally we mention a curious connection between bounded twin-width and small classes.
In 1941, Claude Shannon introduced a continuous-time analog model of
computation, namely the General Purpose Analog Computer (GPAC). The
GPAC is a physically feasible model in the sense that it can be
implemented in practice through the use of analog electronics or
mechanical devices. It can be proved that the functions computed by a
GPAC are precisely the solutions of a special class of differential
equations where the right-hand side is a polynomial. Analog computers
have since been replaced by digital counterpart. Nevertheless, one can
wonder how the GPAC could be compared to Turing
machines.
Suppose that you want to check whether a graph satisfies some (graph) property. The goal is to minimize the number of queries to the adjacency matrix. You are given as an “untrusted hint” an isomorphic copy of the graph. You must always be correct, but the number of queries made is only measured when the hint is correct. Do such unlabeled certificates help? In the worst case? Per instance?
Informal presentation.
Informal presentation.
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.
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.
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).
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…)
*

#### Année 2021

Algorithmes et structures discrètes

Mardi 16 novembre 2021, 13 heures 30, Room 234C, Halle aux farines

**Pole Day** (ASD) *Journée du pôle Algorithmes et structures discrètes 2021*

Tuesday November 16, 2021 · Room 234C, Halle aux farines

13:30-14:00 - Mikael Rabie 14:00-14:30 - Matej Stehlik

14:40 – 15:10 Informal introduction of new postdocs and docs

15:15-15:45 - Adrian Vladu 15:45-16:15 - Simon Apers 16:15 Goûter (à l'IRIF)

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*

*
*