Seminar "Algorithms of Saclay Plateau"

Le treillis de Tamari est un ordre partiel sur les objets Catalan. De nombreuses descriptions de ce treillis donnent lieu à de nombreuses familles de généralisations, notamment les treillis m-Tamari, nu-Tamari et m-Cambriens. Après une “visite guidée” dans ce zoo des généralisations du treillis de Tamari, je présenterai mon travail de thèse. Je parlerai en particulier d’une nouvelle famille d’ordres partiels appelés alt nu-Tamari, généralisant le treillis de Tamari, et de l’étude de leurs intervalles linéaires, ainsi que d’une conjecture de Stump-Thomas-Williams stipulant que le nombre d’intervalles dans le treillis m-Cambrien en type A linéaire est le même que dans le treillis m-Tamari, et de mes avancées sur ce sujet.

Given a random Δ-regular graph G, it holds that χ(G) ∼ Δ / (2 ln Δ) with high probability. However, for any ε > 0 and k large enough, no (randomised) polynomial-time algorithm returning a proper k-colouring of such a random graph G is known to exist when k < (1−ε) Δ / ln Δ, while a greedy algorithm can return a proper k-colouring when k > (1+ε) Δ / ln Δ. One of the reasons that could explain this is that the space of proper k-colourings of a random graph is composed of many far-apart clusters when k < (1−ε) Δ / lnΔ, whence the small probability of success of a local search algorithm to find such a colouring. In contrast, when k > (1+ε) Δ / ln Δ, the space of proper k-colourings is well-connected in many aspects. Namely, in that setting, given a random Δ-regular graph G and a random k-colouring of G, with high probability one can recolour any vertex of G with any colour by recolouring only a sublinear fraction of the vertices. With respect to proper colourings, sparse graphs share many extremal properties with random graphs. In 2019, Molloy used entropy compression (an algorithmic version of the Lovász Local Lemma introduced in 2010 by Moser and Tardos) to construct a randomised polynomial-time algorithm that yields a proper k-colouring of any triangle-free G of maximum degree Δ, with k = (1+o(1)) Δ / ln Δ as Δ → ∞. In this presentation, I will show that, with high probability, in a uniformly random proper k-colouring of G all but a small fraction of the vertices can be recoloured to any colour by recolouring only their neighbours. The same holds with high probability for every vertex if we require that the girth of G is large enough and recolour its neighbourhood up to a small distance.

To color a graph properly, one needs at least as many colors as the size of its biggest clique; therefore, the chromatic number χ is lower-bounded by the clique number ω In general, there are no upper bounds on χ in terms of ω. The graphs for which we can approximate the chromatic number with ω ≤ χ ≤ f(ω) for some function f are called χ-bounded graphs and the optimal function f is called the χ-binding function. A class of graphs that has been the object of many studies in structural graph theory is the class of segment graphs: a segment graph is formed by a collection of straight line segments in the plane where the vertices are the segments and there is an edge between two intersecting segments. If the segments are all parallel, then it is also called an interval graph, known for being perfect (χ = ω). In the 70s, Erdös asked if we allow segments to have different slopes, then can we still approximate χ with ω, i.e. are segment graphs χ-bounded? In 2014, Pawlik, Kozik, Krawczyk, Lasón, Micek, Trotter, and Walczak showed a construction of a triangle-free graph (ω = 2) with arbitrarily large chromatic number, answering Erdös question in the negative. However, if one only allows the segments to have d different slopes (d-directional segment graphs), then it is easy to color the graph with dω colors since each slope induces an interval graph. Bhattacharya, Dvorák and Noorizadeh conjectured that dω is optimal, meaning that there exists d-directional segment graphs for which χ = dω for every d and every ω. In this seminar, we will show the χ-binding function of d-directional segment graphs, which confirms the conjecture for even ω and refutes it for odd ω.

In the capacitated vehicle routing problem, we are given a metric space with a vertex called depot and a set of vertices called terminals. The goal is to find a minimum length collection of tours starting and ending at the depot such that each tour visits at most k terminals, and each terminal is visited by some tour. In this talk, I am going to talk about recent progress on the capacitated vehicle routing problem on trees and in the two-dimensional Euclidean plane.

Church’s Problem asks for the construction of a procedure which, given a logical specification φ(I, O) between input ω-strings I and output ω-strings O, determines whether there exists an operator F that implements the specification in the sense that φ(I, F(I)) holds for all inputs I. Büchi and Landweber gave a procedure to solve Church’s problem for MSO specifications and operators computable by finite-state automata. We investigate a generalization of the Church synthesis problem to the continuous time of the non-negative reals. It turns out that in the continuous time there are phenomena which are very different from the canonical discrete time domain of the natural numbers.

Anomaly detection is vital in many domains, such as finance, healthcare, and cybersecurity. In this paper, we propose a novel deep anomaly detection method for tabular data that leverages Non-Parametric Transformers (NPTs), a model initially proposed for supervised tasks, to capture both feature-feature and sample-sample dependencies. In a reconstruction-based framework, we train the NPT to reconstruct masked features of normal samples. In a non-parametric fashion, we leverage the whole training set during inference and use the model’s ability to reconstruct the masked features to generate an anomaly score. To the best of our knowledge, this is the first work to successfully combine feature-feature and sample-sample dependencies for anomaly detection on tabular datasets. Through extensive experiments on 31 benchmark tabular datasets, we demonstrate that our method achieves state-of-the-art performance, outperforming existing methods by 1.7\% and 1.2\% in terms of F1-score and AUROC, respectively. Our ablation study provides evidence that modeling both types of dependencies is crucial for anomaly detection on tabular data.

Verification of discrete time or continuous time dynamical systems is known to be undecidable. However, undecidability is known not to hold for robust systems: if robustness is defined as the fact that the reachability relation is stable under infinitesimal perturbation, then decidability holds. Similarly, while undecidability holds for logical formulas over the reals, it does not when considering $\delta$-undecidability, i.e. when properties are either true or delta-far from being true. We first relate these notions of robustness. Then, we extend these statements at the complexity level: When a system is robust, it makes sense to quantify at which level of perturbation a system is robust. We prove assuming robustness to polynomial perturbation on precision leads to PSPACE and even to a characterization of PSPACE. We prove assuming robustness to polynomial perturbation on time or length leads to similar statements but with PTIME. We also relate this to analogue models of computation.

The idea of considering analog models of computation (by opposition to today’s digital models) is not new, and actually the first ever built computer were analog. Some well-known models of analog computers have been proposed, such as the GPAC (General Purpose Analog Computer) of Claude Shannon in 1941. However, these models have been mostly forgotten as they were 1) thought to be less powerful than a modern computer 2) not as good as modern computers for doing precise computations. But it turns out that 1) is wrong, and this was proved only a decade ago, and analog computers could even solve some problems faster and 2) that many modern applications of computers are precisely contexts, such as machine learning or deep learning, where precision is not so important. What matters most is speed and energy consumptions, which are precisely the strength of analog computers. Actually, analog computing comes historically also from the idea of computing by analogy. We will review various recent rebirth of analog computing and analog models, including recent startups proposing very fast computing for deep learning, or (re)birth of models based on analog computing, such as neural ordinary differential equations, or explanations of performances of some digital models through the eyes of analog computing.

The number one criticism of average-case analysis is that we do not actually know the probability distribution of real-world inputs. Thus, analyzing an algorithm on some random model has no implications for practical performance. At its core, this criticism doubts the existence of external validity, i.e., it assumes that algorithmic behavior on the somewhat simple and clean models does not translate beyond the models to practical performance real-world input. With this paper, we provide a first step towards studying the question of external validity systematically. To this end, we evaluate the performance of six graph algorithms on a collection of 2745 sparse real-world networks depending on two properties; the heterogeneity (variance in the degree distribution) and locality (tendency of edges to connect vertices that are already close). We compare this with the performance on generated networks with varying locality and heterogeneity. We find that the performance in the idealized setting of network models translates surprisingly well to real-world networks. Moreover, heterogeneity and locality appear to be the core properties impacting the performance of many graph algorithms

In 2002, Leslie Valiant designed a computational model based on counting the number of perfect matchings of weighted graphs: the matchgates. Matchgates can directly be interpreted as quantum processes providing an original combinatorial approach to quantum computing. In the general case, counting perfect matchings is #P-complete. However, in the specific case of planar graphs, the FKT-algorithm allows counting perfect matchings in polynomial time. As a consequence, planar matchgates provide a class of quantum computation that can be classically simulated in polynomial time.Completely independently, in 2010, as a part of the categorical quantum mechanics program, Coecke and Kissinger introduced the ZW-calculus, a graphical language inspired by two kinds of entanglement, the GHZ-states and W-states. This calculus quickly demonstrated interesting algebraic properties allowing it to be the first graphical language to be proven universal and complete for all linear maps. In this talk, I will present joint works with Étienne Moutot, Thomas Perez and Renaud Vilmart, building a bridge between the two formalisms: matchgates and ZW-calculus. It appears that reformulating matchgate theory into the category-theoretic framework of ZW-calculus allows for a much simpler presentation. Conversely, the matchgate approach provides the ZW-calculus with a straightforward combinatorial interpretation. I will introduce a fragment of ZW-calculus, the planar W-calculus, and show that it is universal and complete for matchgates. Then I will present a variety of consequences, from new algorithms for perfect matching counting and quantum simulation to a diagrammatical approach to determinant theory.

The performance of Evolutionary Algorithms (EAs) in dynamic environments, that is, environments in which the fitness function changes over time, has recently been studied (e.g., [Lengler, Meier, 2020]). In this talk, we develop and analyse a minimal example TwoLinear of a dynamic environment that can be hard for EAs. The environment consists of two linear functions f1 and f2 with positive weights 1 and n, and in each generation selection is based on one of them at random. They only differ in the set of positions that have weight 1 and n. We show that the (1+1)-EA with mutation rate χ/n is efficient for small χ on TwoLinear, but does not find the shared optimum in polynomial time for large χ.To obtain the above result, we apply drift analysis in two dimensions. Drift analysis is one of the most powerful techniques to analyse the performance and behaviour of EAs. Previously, it has only been applied in one dimension. Here, we are in the case of two random variables X1, X2, and the drift is approximatively given by A·(X1, X2)T for a matrix A. More precisely, we are in the case where X1 and X2 impede each other’s progress, and we give a full characterisation of this case.

We examine and clarify in detail the contributions of Yoshisuke Matsunaga (1694?–1744) to the computation of Bell numbers in the eighteenth century (in the Edo period), providing modern perspectives to some unknown materials that are by far the earliest in the history of Bell numbers. Later clarification and developments by Yoriyuki Arima (1714–1783), and several new results such as the asymptotic distributions (notably the corresponding local limit theorems) of a few closely related sequences are also given.

“The totalization process was introduced by Denjoy in 1912 as an interative procedure to obtain the antiderivative of any derivative. This idea has generated the notion of Denjoy integral, first of a serie of notions of integration proposed in literature as alternatives to Riemann and Lebesgue integrals in order to successfully retrieve the antiderivative of some class of pathological derivatives. This talk follows the path taken by Denjoy, describing the details of its solution for the problem of integration, and applies it to the realm of first order ODEs, exploring the set theoretical complexity of obtaining the solution of the dynamical system for ODEs with specific pathological right-hand terms.”

“Bootstrap percolation is a classical model for the spread of information in a network. In the round-based version, nodes of an undirected graph become active once at least r neighbors were active in the previous round. We consider a slightly modified variant, acting on graphs that contain two types of edges—modeling local and global interactions, respectively. In this model, information spreads immediately via local edges but still requires a certain number r of active neighbors in order to spread via global edges. We show for certain graph classes that this modified process, when starting with a single active node, results in a phase transition with respect to how quickly further nodes are activated. Initially, the spread is rather slow, but it gains significant speed once global edges are being used to activate nodes.”

“In order to understand better how and why crossover can benefit optimization, we consider pseudo-Boolean functions with an upper bound 𝐵 on the number of 1s allowed in the bit string (cardinality constraint). We consider the natural translation of the OneMax test function, a linear function where 𝐵 bits have a weight of 1 + 𝜀 and the remaining bits have a weight of 1. The literature gives a bound of Θ(𝑛^2) for the (1+1) EA on this function. Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping both a 1 and a 0. The experimental literature proposes balanced operators, preserving the number of 1s, as a remedy. We show that a balanced mutation operator optimizes the problem in 𝑂 (𝑛 log 𝑛) if,𝑛 − 𝐵 = 𝑂 (1). However, if 𝑛 − 𝐵 = Θ(𝑛), we show a bound of Ω(𝑛^2), just as classic bit flip mutation. Crossover and a simple island model gives 𝑂 (𝑛^2/log 𝑛) (uniform crossover) and 𝑂 (𝑛√𝑛) (3-ary majority vote crossover). For balanced uniform crossover with Hamming distance maximization for diversity we show a bound of 𝑂 (𝑛 log 𝑛).”

In the first part of the presentation I will introduce the concept of analog computation in relation with integrator devices used in the 1940’s to compute simple operations, called differntial analyzers. A description of the theoretical model behind the behaviors of those machine was first provided by Shannon, with his GPAC model which stands for Generable Purpose Analog Computation model. I will describe some of the main modifications that have been later applied in litterature to the model in order to simplify its formulation and improve its computational power. Following this guideline, I will then explain how these modifications led to an equivalence between this model and the setting of computable analysis, meaning that every function that can be computed within the computable analysis framework can also be computed by the GPAC model, and viceversa. During the course of this first, introductory, part of the talk, the motivations at the core of this research will be discussed as well. In the second part of the presentation I will illustrate how, with the correct improvements to the notion of computation of the GPAC model, this particular equivalence can be extended to the case of polynomial time complexity, leading to an equivalence between the well known complexity calss P and a certain class of systems of ODEs. To obtain this result it is required a way to encode and reproduce the behavior of the transiction function of a Turing machine in a continuous setting, keeping bounded the error introduced during this simulation.This second part of the talk will be more quantitative than the first, including more technical details. Finally, in the last part of the presentation, I will briefly mention how the results previuosly showed can be applied to further characterize higher complexity classes, such as EXPTIME or PSPACE, with similar dynamical system.

Very recently, the first mathematical runtime analyses of the multi-objective evolutionary optimizer NSGA-II have been conducted (AAAI 2022, GECCO 2022 (to appear), arxiv 2022). We continue this line of research with a first runtime analysis of this algorithm on a benchmark problem consisting of two multimodal objectives. We prove that if the population size $N$ is at least four times the size of the Pareto front, then the NSGA-II with four different ways to select parents and bit-wise mutation optimizes the OneJumpZeroJump benchmark with jump size $2 \le k \le n/4$ in time $O(N n^k)$. When using fast mutation, a recently proposed heavy-tailed mutation operator, this guarantee improves by a factor of $k^{\Omega(k)}$. Overall, this work shows that the NSGA-II copes with the local optima of the OneJumpZeroJump problem at least as well as the global SEMO algorithm.

The Skolem Problem asks how to determine algorithmically whether a given linear recurrence sequence (such as the Fibonacci numbers) has a zero. It is a central question in dynamical systems and number theory, and has many connections to other branches of mathematics and computer science. Unfortunately, its decidability has been open for nearly a century! In this talk, I will present a survey of what is known on the Skolem Problem and related questions, including recent and ongoing developments.

Effective inclusion of physics-based knowledge into deep neural network models of dynamical systems can greatly improve data efficiency and generalization. Such a priori knowledge might arise from physical principles (e.g., conservation laws) or from the system’s design (e.g., the Jacobian matrix of a robot), even if large portions of the system dynamics remain unknown. We develop a framework to learn dynamics models from trajectory data while incorporating a priori system knowledge as inductive bias. By exploiting a priori system knowledge during training, the proposed approach learns to predict the system dynamics two orders of magnitude more accurately than a baseline approach that does not include prior knowledge, given the same training dataset.

On appelle sous-shift (ou sous-décalage) un ensemble de pavages ou de coloriages du plan respectant certaines contraintes locales. Historiquement introduits comme discrétisations de systèmes dynamiques continus, on se propose ici d’en étudier un invariant topologique, introduit par W.Geller et J.Propp, le Groupe Fondamental Projectif. A l’instar de la définition habituelle du groupe fondamental, un invariant d’espaces topologiques, il s’agira ici de comprendre comment l’on peut définir une notion de chemins dans les pavages, reliant les configurations entre elles, et d’étudier comment les déformations de ces chemins permettent d’associer à chaque pavage un unique objet algébrique: son groupe fondamental projectif. En particulier, on montrera dans cet exposé comment réaliser une large classe de groupes comme groupes fondamentaux de certains pavages.

One important research endeavour at the intersection of circuit complexity theory, algebraic automata theory and logic is the classification of regular languages according to their localisation within the internal structure of NC^1, the class of languages decided by Boolean circuits of polynomial size, logarithmic depth and with gates of constant fan-in. In some sense, the search for such a classification concentrates most of the open questions we have about the relationship between NC1 and its well-studied subclasses.

While many questions are still open, one of the greatest successes of this research endeavour has been the characterisation of the regular languages in AC^0, the subclass of NC^1 corresponding to Boolean circuits of polynomial length, constant depth and with gates of unbounded fan-in. This characterisation takes the form of a triple languages-algebra-logic correspondence: a regular language is in AC0 if and only if its syntactic morphism is quasi-aperiodic if and only if it is definable in first-order logic over words with linear order and modular predicates.

It is natural to try to extend such results to classes of formal languages greater than the class of regular languages. A well studied and robust such class is given by visibly pushdown languages (VPLs): languages recognised by pushdown automata where the stack-height-behaviour only depends on the letters read from the input. Over the previous decade, a series of works concentrated on the fine complexity of VPLs, with several achievements: one of those was a characterisation of the class of visibly counter languages (basically VPLs recognised by visibly pushdown automata with only one stack symbol) in AC^0 by Krebs, Lange and Ludwig. However, the characterisation of the VPLs in AC^0 still remains open.

In this talk, I shall present a conjectural characterisation of the VPLs in AC^0 obtained with Stefan Göller at the Universität Kassel. It is inspired by the conjectural characterisation given by Ludwig in his Ph.D. thesis as a generalisation of the characterisation for visibly counter languages, but that is actually false. In fact, we give a more precise general conjectural characterisation that builds upon recognisability by morphisms into Ext-algebras, an extension of recognisability by monoid-morphisms proposed by Czarnetzki, Krebs and Lange to suit the case of VPLs. This characterisation classifies the VPLs into three categories according to precise conditions on the Ext-algebra-morphisms that recognise them:

• those that are TC^0-hard;
• those that are in AC^0;
• those that correspond to a well-identified class of “intermediate languages” that we believe to be neither in AC^0 nor TC^0-hard.

For many real-world optimization problems, the objective function is only indirectly accessible, for example, via simulations. In this setting, randomized search heuristics (RSHs) are applied to great success, guided solely by the quality of samples. One important class of these heuristics are estimation-of-distribution algorithms (EDAs), which maintain and refine a probabilistic model of the search space.

In this talk, I discuss some of my results on the theoretical analysis of EDAs by presenting properties of EDAs that set them apart from other RSHs. We see that EDAs cope inherently well with noisy objective functions, due to the probabilistic model tolerating faulty updates to a certain degree. However, we also show that these models typically degenerate if important updates are withheld for longer periods of time. We conclude by presenting how this problem is circumvented when applying better rules to handle updates.

The advent of quantum information processing promises dramatic advantages with respect to its classical counterpart, notably for computing. I will give an introduction to quantum computing through the lens of holomorphic functions, which allow us to elegantly describe both discrete- and continuous-variable quantum computations, using classical dynamical systems. As an application, I will discuss the characterisation of quantum properties that are necessary resources for quantum computational advantages, such as non-Gaussianity or entanglement.

Joint work with Saeed Merhaban (arXiv:2111.00117).

Distributed Denial of Service (DDoS) cyberattacks represent a major security risk for network operators and internet service providers. They thus need to invest in security solutions to protect their network against DDoS attacks. The present work focuses on deploying a network function virtualization based architecture to secure a network against an on-going DDoS attack. We assume that the target, sources and volume of the attack have been identified. However, due e.g. to 5G network slicing, the exact routing of the illegitimate flow in the network is not known by the internet service provider. We seek to determine the optimal number and locations of virtual network functions in order to remove all the illegitimate traffic while minimizing the total cost of the activated virtual network functions. We propose a robust optimization framework to solve this problem. The uncertain input parameters correspond to the amount of illegitimate flow on each path connecting an attack source to the target and can take values within a predefined uncertainty set. In order to solve this robust optimization problem, we develop an adversarial approach in which the adversarial sub-problem is solved by a Branch & Price algorithm. The results of our computational experiments, carried out on medium-size randomly generated instances, show that the proposed solution approach is able to provide optimal solutions within short computation times

In this presentation it will be shown how to make use of ordinary differential equations (ODEs) to describe standard complexity classes. Previously it was shown that the classes P and FP can be characterized with ODEs. Here we show that ODEs can also be used to characterize a wide range of computable functions, from exponentials up to including all elementary functions. It will be also discussed the case of space complexity classes, introducing the definition of a particular dynamical system able to describe functions in FPSPACE. Finally, to complement what have been done with functions, the treatment of classes of languages such as EXPTIME and PSPACE will be included in the analysis.

We consider the standard population protocol model, where (a priori) indistinguishable and anonymous agents interact in pairs according to uniformly random scheduling. The self-stabilizing leader election problem requires the protocol to converge on a single leader agent from any possible initial configuration. We initiate the study of time complexity of population protocols solving this problem in its original setting: with probability 1, in a complete communication graph. The only previously known protocol by Cai, Izumi, and Wada [Theor. Comput. Syst. 50] runs in expected parallel time \Theta(n2) and has the optimal number of n states in a population of n agents. The existing protocol has the additional property that it becomes silent, i.e., the agents’ states eventually stop changing.

Observing that any silent protocol solving self-stabilizing leader election requires \Omega (n) expected parallel time, we introduce a silent protocol that uses optimal O(n) parallel time and states. Without any silence constraints, we show that it is possible to solve self-stabilizing leader election in asymptotically optimal expected parallel time of O(log n), but using at least exponential states (a quasi-polynomial number of bits). All of our protocols (and also that of Cai et al.) work by solving the more difficult ranking problem: assigning agents the ranks 1, … ,n.

La complexité de Kolmogorov est utilisée avec succès pour caractériser l’aléatoire pour les chaînes binaires infinies : Il s’agit des chaînes dont la complexité de Kolmogorov de leurs préfixes est maximale. A l’opposé, les chaînes binaires infinies dites “K-triviales” sont celles dont la complexité de Kolmogorov de leurs préfixes est minimale. La classe des K-triviaux est dénombrable, et contient “juste un peu plus” que les chaînes binaires infinies calculables. Les nombreuses études sur les K-triviaux depuis une vingtaine d’années ont révélé la grande richesse de cette classe. Nous en présenterons les différents aspects.

Cellular Automata constitute the most established distributed model of computation on space-time grid. It is clearly physics-like, in the sense that it shares some fundamental symmetries such as homogeneity (invariance of the physical laws in time and space), causality, and often reversibility. When a CA is invariant under a transformation identically performed at every point of the configuration space, they are said to have a global symmetry. Typical global symmetries include reflections, rotations, time inversion. Local symmetries, the cornerstone of gauge theories, is a stronger constraint. I will provide a constructive method, a step-by-step procedure, to make cellular automata invariant under the local action of a gauge group and the notion of gauge-equivalence will be formalized. Then, I will extend such results into the Quantum realm by means of a concrete example. In conclusion, I will discuss how such discrete time and discrete space gauge invariant automata can be described at larger scale, e.g. by differential equations, with and without information loss.

We show how to cope with Big Data by means of Automated Deduction. We generate a Horn or a bijunctive formula from sets of positive and negative tuples T and F, respectively These sets of tuples have been previously shortened to a locally minimal length, provided that the two sets T and F keep an empty intersection. Since the problem to find the minimal length is an NP-optimization problem, we apply different approximation strategies. We also apply two approaches to formula production: (1) the LARGE approach, where only tuples of F falsify the produced formula, and (2) EXACT, where only tuples of T satisfy the formula. In case of the large approach we apply a set cover approximation algorithm to keep the minimal set of clauses falsifying all tuples from the set F. The produced formula can be used to further characterize subsequent sets of tuples and identify their membership among the true or false examples. The whole system, called MCP for Multiple Characterization Problem, has been implemented and can be found at https://github.com/miki-hermann/mcp.

(research done in collaboration with Gernot Salzer, Technische Universität Wien, Vienna, Austria)

A travers une série d’exemples, je décrierai les applications de la recherche opérationnelle et de l’optimisation discrète à Google. Puis je me focaliserai sur l’apport récent des techniques des moteurs SAT (satisfiabilité) et les challenges et opportunités qui lui sont liées.

An Automata Network (AN) consists of a finite digraph and a finite set of states. Each node has a state and updates itself in function of the state of its inbound neighbours. Updates are synchronous and parallel, as in cellular automata.

This model was initially defined in biology, where each node encodes the (non-)expression of a gene. As genes influence each other’s expression, pretty complex dynamics may ensue. Later on, ANs were also considered in fields such as engineering. But surprisingly, the theoretical and general study of ANs from a computer science perspective is rather recent.

In this talk, we will argue that any nontrivial property of the dynamics of a given AN is computationally hard. This parallels the Rice theorem, which states that any nontrivial property of the function computed by a given Turing machine is undecidable.

First, we will spend some time to define ANs and to precisely state the theorem. Then, we will see some insights from the proof that may be reused for other results, maybe with other computational models. Finally, we will give a glimpse of the future, discussing other related results that are currently in preparation.

Submodular and diminishing-returns (DR) submodular optimization are important optimization problems with many real-world applications in machine learning, economics and communication systems. Moreover, DR-submodular optimization captures a subclass of non-convex optimization that provides both practical and theoretical guarantees.

In this talk, we present algorithms with performance guarantees for the fundamental problems of maximizing non-monotone submodular and DR-submodular functions over convex sets in the online environment. In several settings, these guarantees match the currently best-known ones in the offline environment.

It turns out that if you just know what 0, 1, -1 are, as well as an addition, and a multiplication, and if you remember what an ordinary differential equation are, then you can (re-)define, (re-)discover and program many concepts from Mathematics and Computer Science. An even explain many concepts in a very simple(r) way to your kids, colleagues, and even grandmother.

In particular, you can present/rediscover descriptive complexity, computability and complexity using polynomial ordinary differential equations only.

A title for this talk could also be “Programing with Ordinary Differential Equations”, as these questions also relate to analog models of computations, and in particular to the 1941 General Purpose Analog Computer of Claude Shannon, and to the machines at the time of your grandmother, and the forgotten art of their programming.

This also relates to today’s and futuristic computation models with molecules/proteins, such as the one that was awarded the “Prix du journal La Recherche 2019”.

Teaser/Divulgâchage: https://www.lemonde.fr/blog/binaire/2019/02/15/la-revanche-du-calcul-analogique/

The domino problem for a finitely generated group asks whether there exists an algorithm which takes as input a finite alphabet and finitely many Wang tiles, and decides whether there exists a tiling of the group by this set of tiles. I will survey known results and present the domino problem conjecture: finitely generated groups with decidable domino problem are exactly virtually free groups. Then I will explain why this problem is undecidable on surface groups. Joint work with Sebastián Barbieri and Etienne Moutot.

We consider problems in edge- or vertex colored graphs. As an example, the Web graph may be considered as a vertex-colored graph where the color of a vertex represents the content of the corresponding page (red for mathematics, yellow for physics, etc.). When the edges/vertices of graphs are colored, then we talk about c-edge/vertex colored graphs (c is the number of colors), models which in fact generalize various classes of graphs. In general, one can observe that problems related to colored graphs often consist in finding subgraphs such as paths, cycles, matchings and trees, with, in addition, specified constraints on colors.

In the case of c-edge-colored graphs, original problems correspond to extracting subgraphs, for example, Hamiltonian and Eulerian paths or cycles, trees, matchings etc., colored in some specified pattern. Here we survey a series of results concerning colored matchings in c-colored graphs, for arbitrarily c.

In the case of vertex-colored graphs, we deal with tropical subgraphs, a concept with direct applications to the web graph and in bioinformatics. More precisely, given a vertex-colored graph, a tropical subgraph (induced or otherwise) is defined to be a subgraph where each color of the initial graph appears at least once. Notice that in a tropical subgraph, adjacent vertices can receive the same color, thus a tropical subgraph may not be properly colored. Potentially, many graph invariants, such as the domination number, the vertex cover number, maximum matchings, independent sets, connected components, shortest paths, etc. can be studied in their tropical version. This notion is close to, but somewhat different from the colorful (or rainbow) concept (all colors of the subgraph are different) used for paths and elsewhere in vertex/edge-colored graphs. It is also related to the concepts of color patterns (the subgraph has fixed color patterns) used in bio-informatics. Here we explain some results on our ongoing work on colored matchings, tropical paths and tropical connected subgraphs.