Seminar "Algorithms of Saclay Plateau"

To keep informed you can

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

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 https://github.com/miki-hermann/mcp.

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

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

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.