Seminar "Algorithms of Saclay Plateau"

To keep informed you can

Unless otherwise stated, all times below are in Paris local time.

Olivier Bournez

Analog computing is back

Olivier Bournez (LIX)
Thursday 1 June 2023 at 13:00, room Salle Grace Hopper
Invited by the ALCO team, shared with the Proofs and algorithms pole seminar of LIX .

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.

Philipp Fischbeck

On the External Validity of Average-Case Analyses of Graph Algorithms

Philipp Fischbeck (Hasso Plattner Institute, University of Potsdam)
Thursday 16 March 2023 at 10:30, room Salle Emmy Noether
Invited by the ALCO team, shared with the Proofs and algorithms pole seminar of LIX .

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

Titouan Carette

Perfect matchings, quantum computing and monoidal categories

Titouan Carette (University of Latvia)
Thursday 9 March 2023 at 10:30, room Salle Grace Hopper
Invited by the ALCO team, shared with the Proofs and algorithms pole seminar of LIX .

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.

Two-Dimensional Drift Analysis: Optimizing Two Functions Simultaneously Can Be Hard

Duri Andrea Janett (LIX)
Thursday 5 January 2023 at 11:00, room Salle Philippe Flajolet
Invited by the ALCO team, shared with the Proofs and algorithms pole seminar of LIX .

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.

Bell numbers in Matsunaga's and Arima's Genjikō combinatorics: Modern perspectives and local limit theorems

Hsien-Kuei Hwang (LIX)
Wednesday 9 November 2022 at 11:00, room Grace Hopper
Invited by the Alco team, shared with the Proofs and algorithms pole seminar of LIX .

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.

Totalization of Ordinary Differential Equations

Riccardo Gozzi (LIX)
Wednesday 19 October 2022 at 11:00, room Grace Hopper
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

“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.”

Martin Krejca

Accelerated Information Dissemination on Networks with Local and Global Edges

Martin Krejca (LIX)
Thursday 13 October 2022 at 11:30, room Nicolaas Govert de Bruijn
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

“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.”

Simon Wietheger

Crossover for Cardinality-Constrained Optimization

Simon Wietheger (Hasso Plattner Institute)
Friday 7 October 2022 at 11:30, room Poincaré
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

“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 𝑛).”

Analog characterization of complexity classees

Riccardo Gozzi (LIX)
Tuesday 21 June 2022 at 11:00, room Grace Hopper
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

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.

A First Runtime Analysis of the NSGA-II on a Multimodal Problem

Zhongdi QU (LIX)
Tuesday 21 June 2022 at 14:00, room Philippe Flajolet
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

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.

Joël Ouaknine

The Skolem Landscape

Joël Ouaknine (Max Planck Institute for Software Systems, Saarbrücken, Germany)
Thursday 19 May 2022 at 14:30, room LIX Sophie Germain + online upon request
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

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.

Franck Djeumou

Neural Networks with Physics-Informed Architectures and Constraints for Dynamical Systems Modeling

Franck Djeumou (Department of Electrical and Computer Engineering at the University of Texas at Austin)
Thursday 14 April 2022 at 15:00, online seminar
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

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.

Groupe fondamental et pavages du plan: quelques constructions

Léo Paviet Salomon (Greyc, Caen)
Thursday 24 March 2022 at 11:00, room Salle Henri Poincaré (recording available)
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

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.

Nathan Grosshans

Visibly pushdown languages in AC^0

Nathan Grosshans (Universität Kassel, Germany.)
Thursday 17 March 2022 at 11:00, online seminar
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

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.
Martin Krejca

The Power of Probabilistic Models in Optimization

Martin Krejca (LIP 6)
Thursday 17 February 2022 at 11:00, room Salle Philippe Flajolet
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

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.

Ulysse Chabaud

Holomorphic Quantum Computing

Ulysse Chabaud (Institute for Quantum Information and Matter, Caltech, US)
Thursday 3 February 2022 at 16:30, online seminar
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

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

Sonia Vanier

Distributed Denial of Service cyber-attacks in 5G networks: a robust approximation approach

Sonia Vanier (Délégation au LIX, et Université Paris, Panthéon-Sorbonne)
Thursday 24 June 2021 at 14:30, online seminar
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

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

Analog characterization of standard complexity classes by means of ODEs

Riccardo Gozzi (Instituto Superior Técnico, Portugal)
Wednesday 12 May 2021 at 10:30, online seminar
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

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.

Janna Burman

Time-Optimal Self-Stabilizing Leader Election in Population Protocols

Janna Burman (LISN, Université Paris-Saclay)
Thursday 8 April 2021 at 14:30, online seminar
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

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.

Benoit Monin

Une petite histoire de la K-trivialité

Benoit Monin (Université de Créteil)
Thursday 1 April 2021 at 14:30, online seminar
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

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.

Giuseppe Di Molfetta

Gauge-invariance in celullar automata and multi-scales analysis

Giuseppe Di Molfetta (Aix-Marseille University)
Thursday 18 March 2021 at 14:30, online seminar
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

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.

Miki Hermann

Logical Analysis of Data

Miki Hermann (LIX)
Thursday 18 February 2021 at 14:30, online seminar
Invited by the AlCo team, shared with the Proofs and algorithms pole seminar of LIX .

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

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

Laurent Perron

Recherche Opérationnelle à Google

Laurent Perron (Google)
Thursday 12 March 2020 at 14:30, room LRI, room 445

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.

Guilhem Gamard

Rice-like theorems in Automata Networks

Guilhem Gamard (LIS, Université Aix-Marseille.)
Thursday 20 February 2020 at 14:30, room LIX, room Henri Poincaré

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.

Nguyễn Kim Thắng

Online Non-monotone Submodular Maximization: Approximation and Regret Guarantees

Nguyễn Kim Thắng (IBISC)
Thursday 6 February 2020 at 14:30, room LIX, room Grace Hopper

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.

Olivier Bournez

Calcul analogique/ Analog computations / Computing with proteins or with ordinary differential equations.

Olivier Bournez (LIX)
Thursday 14 November 2019 at 14:30, room IBISC, petit amphi, bâtiment IBGBI, 23 boulevard de France, Evry

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”.


Nathalie Aubrun

The Domino Problem is undecidable on surface groups.

Nathalie Aubrun (ENS-Lyon, CNRS)
Friday 27 September 2019 at 14:30, room LRI, salle 445

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.

Yannis Manoussakis

Matchings and related structures with Specified Color Properties In Vertex- or Edge-colored Graphs.

Yannis Manoussakis (University Paris South and CNRS)
Thursday 17 October 2019 at 14:30, room LRI, salle 445

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.