~~NOCACHE~~ /* DO NOT EDIT THIS FILE */ [[en:seminaires:asd:index|Algorithms and discrete structures]]\\ Tuesday May 26, 2020, 11AM, 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 [[en:seminaires:asd:index|Algorithms and discrete structures]]\\ Monday January 27, 2020, 9:30AM, 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. [[en:seminaires:asd:index|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// \\ 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