Séminaire Pôle Algorithmes et structures discrètes Équipe thématique Algorithmes et complexité Équipe thématique Combinatoire Équipe thématique Théorie et algorithmique des graphes Gestion des séances 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) Guillaume Chapuy Enrica Duchi Pierre Fraigniaud Sophie Laplante Reza Naserasr Séances passées Année 2024 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 Planted Clique Conjecture states that no polynomial-time algorithm can find a k-clique in an n-vertex Erdős-Rényi random graph with a k-clique planted for $k << n^{1/2}$. We present the equivalence among many variants of planted clique conjectures, including search versions of a success probability exponentially close to 1 and with a non-negligible success probability, a worst-case version (the k-clique problem on incompressible graphs), and decision versions with small and large probabilities. In particular, this equivalence identifies the optimality of a simple edge counting algorithm: By counting the number of edges, one can efficiently distinguish an n-vertex random graph from a random graph with a k-clique planted with probability $k^2/n$ for any $k \le n^{1/2}$. We show that for *any* k, no polynomial-time algorithm can distinguish these two random graphs with probability significantly larger than $k^2/n$ *if and only if* the planted clique conjecture holds. Joint work with Nobutaka Shimizu. Paper: https://eccc.weizmann.ac.il/report/2024/058/ 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)? Computational problems exhibit a diverse range of behaviors in terms of how quickly and effectively they can be solved. What underlying mathematical structure (or lack thereof) in a computational problem leads to an efficient algorithm for solving it (or dictates its intractability)? Given the vast landscape of problems and algorithmic approaches, it would be simplistic to hope for a universal theory explaining the underpinnings of easiness/hardness. Yet, in the realm of constraint satisfaction problems (CSP), the algebraic dichotomy theorem gives a definitive answer: a polynomial time algorithm exists when there are non-trivial local operations called polymorphisms under which the solution space is closed; otherwise the problem is NP-complete. 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 Lettericity is a graph parameter measuring how close a graph is to a word and geometric griddability measures how close a permutation is to a monotone permutation. Both of these parameters enjoy nice properties, in particular graphs of lettericity k are definable in Monadic second-order logic and permutations that are geometric M-griddability are in bijection with a regular language. I will first present both and some properties, and show that these seemingly unrelated parameters are in fact equivalent in permutation graphs, i.e., a permutation class has small geometric griddability iff the associated permutation graph class has small lettericity. Algorithmes et structures discrètes Mercredi 5 avril 2023, 15 heures, 3052 Lélia Blin (LIP6) Self-Stabilizing Distributed Algorithms In the context of large-scale networks, fault tolerance is a necessity. Self-stabilization is an algorithmic approach to fault tolerance in distributed systems. Its aim is to manage processors' memory corruption due to transient failures. The efficiency of a self-stabilizing algorithm is characterized by several parameters, including (1) the time taken by the system to return to a legal configuration after an arbitrary corruption of its processors' memory, and (2) the memory space used by the processors to execute the algorithm. Minimizing memory space is motivated by many aspects, such as networks (e.g. sensor networks) with limited memory space, minimizing data exchanges between processors, and limiting information storage to use redundancy techniques. This seminar will present self-stabilization through two main classical problems: constructing spanning trees, especially those of minimum weight, and electing a leader. It will cover the links between self-stabilization and distributed decision techniques, including computing lower bounds on memory space needed to solve the aforementioned problems using self-stabilizing algorithms. Algorithmes et structures discrètes Mercredi 22 mars 2023, 15 heures, 3052 Michail Lampis (LAMSADE) First Order Logic on Pathwidth Revisited Again Courcelle's theorem, which states that all MSO-expressible properties can be decided in linear time on graphs of bounded treewidth, is one of the most celebrated results in parameterized complexity, because it implies the existence of linear-time FPT algorithms for a host of NP- hard problems. Unfortunately, the hidden constant implied by this theorem is a tower of exponentials whose height increases with each quantifier alternation in the formula. 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 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 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 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. 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 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. 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 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. 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 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? 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) Informal presentation. 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) Informal presentation. 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 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. Algorithmes et structures discrètes Jeudi 9 mai 2019, 15 heures, Salle 1007 Amélie Gheerbrant (IRIF) Graph query languages 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. Algorithmes et structures discrètes Mardi 19 février 2019, 11 heures, Salle 3052 Danupon Nanongkai (KTH) Distributed Shortest Paths, Exactly 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). 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 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…)