Agenda - archives
Conference : Séminaire CANA : Célia Biane Fourati
12/12/2023 à 00h00
Où : Salle 04.05, bât TPR2, LuminyTitre: Biological networks: from Boolean models in computational precision oncology to experimental neurosciences
Résumé : Boolean dynamical models of biological signaling and transcriptional networks have been used these last years to model tumor cells and predict therapeutic targets in Cancer. Major limitations to a more generalised application of these types of models include: 1. the step of models’ reconstruction that is currently done by manual curation of biological knowledge from the litterature by experts in molecular biology, which makes it a long process, dependent on the choices of the modeler and difficult to reproduce. 2. The development of performing algorithmic methods allowing the reprogramming of the dynamical behavior of Boolean dynamical systems. In the course of this seminar, I will address the reconstruction of Boolean biological models from omics data, methods of reprogramming of dynamical behavior of dynamical systems and the application of such approaches to the discovery of new therapeutic targets in cancer. In a second part of the talk, I will introduce concepts from neurosciences and present recently published results on the integrative properties of cerebellar neurons.
Seminaire : Séminaire ACS - Michel Fliess
07/12/2023 à 14h00
Séminaire de Michel Fliess à Toulon "Atténuer les congestions internet grâce aux outils de l'automatique" RÉSUMÉ.- Active Queue Management (AQM) for mitigating Internet congestion has been addressed via various feedback control syntheses, especially P, PI, and PID regulators, by using a linear approximation where the round trip time, i.e., the delay, is assumed to be constant. This constraint is lifted here by using a nonlinear modeling with a variable delay, introduced more than 20 years ago. This delay, intimately linked to the congestion phenomenon, may be viewed as a flat output. All other system variables, especially the control variable, i.e., the packet loss ratio, are expressed as a function of the delay and its derivatives: they are frozen if the delay is kept constant. This flatness-like property, which demonstrates the mathematical discrepancy of the linear approximation adopted until today, yields also our control strategy in two steps: Firstly, designing an open-loop control, thanks to straightforward Flatness-Based Control (FBC) techniques, and secondly, closing the loop via Model-Free Control (MFC) in order to take into account severe model mismatches, like, here, the number of TCP sessions. Several convincing computer simulations, which are easily implementable, are presented and discussed.Seminaire : Séminaire CANA : Timothée Hoffreumon
05/12/2023 à 14h00
Où : Salle 04.05, bât TPR2, LuminyTitre : Projective characterization of higher-order quantum theory
Résumé : Nesting transformations (or logic gates) is a common concept in computer science as some gates may depend on other gates. A typical example of this is the switch gate: it takes two gates as inputs and applies them on a target bit in an order controlled by another bit. Nothing forbids a priori to devise the analogous paradigm in quantum computing. But, contrastingly with the classical case, higher-order quantum transformations lead to the phenomenon of indefinite causal order (ICO) as previous works on the matter have shown. In the same way that a quantum state can be superposed between several values, hence indefinite, the order in which quantum transformations are applied on a quantum state can become superposed between several orderings, hence in ICO. For example, the quantum switch gate takes two transformations A and B as inputs and applies them on a target qubit in an order determined by a control qubit: if the control is 0, A then B are applied on the target; and if the control is 1, it is B then A. When the control qubit is in a superposed state, then the ordering becomes superposed between A then B and B then A.
Therefore, extending quantum theory in a computer-science-motivated manner revealed ICO, a feature believed to be a prerogative of quantum gravity. In addition to this transversal aspect, ICO is also useful for practical purposes, as it was shown to provide an advantage for a variety of tasks in many fields such as quantum computing, information, metrology, and communications.
The goal of this talk is to present a framework that formalizes and characterizes higher-order quantum theory. The two main questions answered are “Given an operator (which mathematically represents all kinds of quantum transformations), does it represent a higher-order transformation?” and “What is the underlying causal structure(s) of such an object?”. It extends two previous characterizations, one done using type theory, and the other one using category theory. This extension relies in particular on the use of superoperator projectors. These projectors have a twofold advantage: first, they make the characterization more straightforward as one can answer the first question simply by applying the projector corresponding to a given higher-order object on the operator. Second, they offer an intuitive explanation of the type-theoretic semantics of higher order: they are the algebraic rules for composing these projectors.
Seminaire : Séminaire ACS - Alessandro Scagliotti
30/11/2023 à 14h00
Séminaire de Alessandro Scagliotti (TUM) à Toulon "Ensemble optimal control: ResNets, diffeomorphisms approximation and Normalizing Flows" Abstract: In the last years it was observed that Residual Neural Networks (ResNets) can be interpreted as discretizations of control systems, bridging ResNets (and, more generally, Deep Learning) with Control Theory. In the first part of this seminar we formulate the task of a data-driven reconstruction of a diffeomorphism as an ensemble optimal control problem. In the second part we adapt this machinery to address the problem of Normalizing Flows: after observing some samplings of an unknown probability measure, we want to (approximately) construct a transport map that brings a “simple” distribution (e.g., a Gaussian) onto the unknown target distribution. In both the problems we use tools from $\Gamma$-convergence to study the limiting case when the size of the data-set tends to infinity.Seminaire : Séminaire CANA : Augusto Modanese
28/11/2023 à 14h00
Où : Salle 04.05, bât TPR2, LuminyTitre : Testing Spreading Behavior in Networks with Arbitrary Topologies
Résumé : Inspired by the works of Goldreich and Ron (J. ACM, 2017) and Nakar and Ron (ICALP, 2021), we initiate the study of property testing in dynamic environments with arbitrary topologies. Our focus is on the simplest non-trivial rule that can be tested, which corresponds to the 1-BP rule of bootstrap percolation and models a simple spreading behavior: Every “infected” node stays infected forever, and each “healthy” node becomes infected if and only if it has at least one infected neighbor. We show various results for both the case where we test a single time step of evolution and where the evolution spans several time steps. In the first, we show that the worst-case query complexity is O(Δ/ε) or Õ(√n/ε) (whichever is smaller), where Δ and n are the maximum degree of a node and number of vertices, respectively, in the underlying graph, and we also show lower bounds for both one- and two-sided error testers that match our upper bounds up to Δ=o(√n) and Δ=O(n^{1/3}), respectively. In the second setting of testing the environment over T time steps, we show upper bounds of O(Δ^{T−1}/εT) and Õ(|E|/εT), where E is the set of edges of the underlying graph. All of our algorithms are one-sided error, and all of them are also time-conforming and non-adaptive, with the single exception of the more complex Õ(√n/ε)-query tester for the case T=2.
Seminaire : Séminaire ACRO : Christopher Thraves (27 novembre, 10h)
27/11/2023 à 10h00
Titre : Separating path systems in trees Résumé : For a graph $G$, an edge-separating (resp. vertex-separating) path system of $G$ is a family of paths in $G$ such that for any pair of edges $e_1, e_2$ (resp. pair of vertices $v_1, v_2$) of $G$ there is at least one path in the family that contains one of $e_1$ and $e_2$ (resp. $v_1$ and $v_2$) but not the other. In this talk, we will see how to determine the size of a minimum edge-separating path system of an arbitrary tree $T$ as a function of its number of leaves and degree-two vertices. Also, we will present bounds for the size of a minimal vertex-separating path system for trees, which we show to be tight in many cases. Finally, we will give similar results for a variation of the definition, where we require the path system to separate edges and vertices simultaneously.Seminaire : Demi-journée du Pole Calcul : Logique et méthodes formelles
23/11/2023 à 09h30
Le premiere demi-journée du Pole-Calcul en 2023-24 sur le thématique "Logique et méthodes formelles"Programme:
9:30 - 10:30
Speaker : Nicolas Peltier (CR CNRS, LIG Grenoble)
Title : A proof procedure in separation logic with inductive definitions.
Abstract: Separation logic is used in program verification to facilitate reasoning on the dynamically allocated memory. In this talk, I will review recent results concerning the automation of reasoning in Separation logic with inductively defined predicates. In particular I will focus on an inductive proof procedure that is sound, complete and terminating for a fragment of inductive definitions satisfying the so called PCE conditions (Progress, Connectivity, Establishment).
Pause-Cafe : 10:30-11:00
11:00 - 11:30
Speaker : Clara Bertolissi (LIS)
Title : Access control policies specification and analysis
Abstract: Access control is a fundamental aspect of computer security; it aims at protecting resources from non-authorised users. The generalised use of access control in modern computing environments has increased the need for high-level declarative languages that enable security administrators to specify a wide range of policy models. In this talk we introduce the main notions of access control and define a declarative meta-model, called CBAC, able to subsume many of the most well known access control models (e.g., MAC, DAC, RBAC). We also design a graphical representation of CBAC policies that aims at easing the specification and verification tasks for security policy administrators. Using such representation of policies, answers to usual administrator queries can be automatically computed, and several properties of access control policies checked.
11:30 - 12:00
Speaker : Cameron Calk (Postdoc, LIS)
Title : Coherence via rewriting in higher Kleene algebras.
Abstract : Squier’s coherence theorem and its generalisations provide a categorical interpretation of contracting homotopies via confluent and terminating rewriting. In particular, this approach relates standardisation to coherence results in the context of higher dimensional rewriting systems. On the other hand, modal Kleene algebras (MKAs) have provided a description of properties of abstract rewriting systems, and classic (one-dimensional) consistency results have been formalised in this setting. In this talk, I will recall the notion of higher Kleene algebra, introduced as an extension of MKAs, and which provide a formal setting for reasoning about (higher dimensional) coherence proofs for abstract rewriting systems. First, I will briefly discuss how rewriting techniques are captured in MKAs before showing how these techniques may be extended to higher dimensions.
Conference : Séminaire CANA : Kostia Chardonnet
21/11/2023 à 14h00
Où : Salle 04.05, bât TPR2, LuminyTitre : The Many-Worlds Calculus: Representing Quantum Control
Résumé : We explore the interaction between two monoidal structures: a multiplicative one, for the encoding of pairing, and an additive one, for the encoding of choice. We propose a PROP to model computation in this framework, where the choice is parametrized by an algebraic side effect: the model can support regular tests, probabilistic and non-deterministic branching, as well as quantum branching, i.e. superposition. The graphical language comes equipped with a denotational semantics based on linear applications, and an equational theory. We prove the language to be universal, and the equational theory to be complete with respect to the semantics.
Seminaire : Séminaire ACRO : Patrice Bertrand (20 novembre, 10h)
20/11/2023 à 10h00
Titre : Convexités d’intervalles et classifications multiniveaux Résumé : Les hiérarchies d’ensembles et la plupart des modèles de classification multiniveau peuvent être caractérisés en termes de convexité d’intervalles. Dans cet exposé, nous introduisons un cadre axiomatique général permettant d’identifier des propriétés de convexité respectivement de la hiérarchie d’Apresjan, de la hiérarchie faible de Bandelt et Dress et de la hiérarchie du lien simple qui sont chacune associées à une dissimilarité arbitraire. En particulier, nous déterminons une filtration respectivement de la hiérarchie du lien simple, de la hiérarchie faible de Bandelt et Dress et de toute convexité d’intervalle contenant la hiérarchie d’Apresjan. Finalement, nous présentons quelques contributions potentielles de cette approche à l’utilisation des méthodes de classification hiérarchique. Bibliographie : P. Bertrand, J. Diatta, An interval convexity-based framework for multilevel clustering with applications to single-linkage clustering, Discrete Appl. Math. 342 (2024) 38-63. F. Brucker, P. Préa, C. Châtel, Totally balanced dissimilarities, J. Classification 37 (2020) 203–222. M. Changat, P.-G. Narasimha-Shenoi, P.-F. Stadler, Axiomatic characterization of transit functions of weak hierarchies, Art Discret. Appl. Math., 2 (2019) #P1.01. J. Diatta, B. Fichet, Quasi-ultrametrics and their 2-Ball Hypergraphs, Discrete Math. 192 (1998) 87–102. B. Fischer, J. Buhmann, Path-based clustering for grouping of smooth curves and texture segmentation, IEEE Trans. Pattern Anal. Mach. Intell. 25 (2003) 513–518.Seminaire : Séminaire CANA : Athénaïs Vaginay
14/11/2023 à 14h00
Où : Salle 04.05, bât TPR2, LuminyTitre: From reaction networks to Boolean networks: why and how
Résumé : One way to get new insights about complex biological systems is to convert between modelling formalisms. Here, we deal with the conversion of reaction networks interpreted with the differential semantics, into Boolean networks. The conversion is particularly challenging, as it requires a drastic change in perspective: from a process-centred description with continuous time and values to a species-centred description with discrete steps and Boolean values. The conversion I present here is based on my PhD work. It aims at preserving properties from the input reaction network, such as its structure (the direct influences between the components) and its binarised transient dynamics (the transitions between the Boolean configurations). We will see how to extract the structure and dynamics of a reaction network, and how to use answer-set programming synthesise complying Boolean networks. So far, the evaluation of the approach on toy examples and real-world reaction networks from the repository BioModels, has demonstrated it effectiveness in synthesising Boolean networks complying with the input reaction networks. It also paved the way of the formal study of the relationship between the differential semantics of reaction network and Boolean networks. The perspectives mainly concern the practical relevance of the Boolean networks we synthesise, as well as the formal exploration of the relationship with other semantics of reaction networks.
Seminaire : Séminaire ACRO : Jérémie Chalopin (06 novembre, 10h)
06/11/2023 à 10h00
Titre: Reconstruire un complexe cubique CAT(0) à partir de sa frontière Résumé: Dans cet exposé, on montrera comment on peut reconstruire un complexe cubique CAT(0) X à partir des distances entre les sommets de sa frontière (les distances étant calculés dans le 1-squelette de X). Cela résout une conjecture récente de Haslegrave, Scott, Tamitegama et Tan (2023). Pour établir ce résultat, on utilise la correspondance entre les complexes cubiques CAT(0) et les graphes médians, ainsi que le fait que les graphes médians admettent un ordre de démontage par coins (on expliquera tout ça pendant l'exposé).Seminaire : Séminaire ACRO : Oscar Defrain (23 octobre, 10h)
23/10/2023 à 10h00
Titre : Enumerating minimal solution sets for metric graph problems Résumé : Problems from metric graph theory such as Metric Dimension, Geodetic Set, and Strong Metric Dimension have recently had a strong impact on the field of parameterized complexity by being the first problems in NP to admit double-exponential lower bounds in the treewidth, and even in the vertex cover number for the latter. We initiate the study of enumerating minimal solution sets for these problems and show that they are also of great interest in enumeration. More specifically, we show that enumerating minimal resolving sets in graphs and minimal geodetic sets in split graphs are equivalent to hypergraph dualization, arguably one of the most important open problems in algorithmic enumeration. This provides two new natural examples to a question that emerged in different works this last decade: for which vertex (or edge) set graph property Π is the enumeration of minimal (or maximal) subsets satisfying Π equivalent to hypergraph dualization? As only very few properties are known to fit within this context---namely, properties related to minimal domination---our results make significant progress in characterizing such properties, and provide new angles of approach for tackling hypergraph dualization. In a second step, we consider cases where our reductions do not apply, namely graphs with no long induced paths, and show these cases to be mainly tractable.Seminaire : Séminaire CANA : Matthew Wilson
17/10/2023 à 14h00
Où : Salle 04.05, bât TPR2, LuminyTitre: Towards Categorical Supermaps
Résumé : In the last two decades, two new perspectives have gained traction in quantum foundations and quantum information theory; each case those perspectives call for a shift in focus from the states of the world to the transformations which act on them. The first perspective is the supermap (also known as process matrix) framework, which by treating standard physical transformations as objects to be manipulated by higher-order transformations, provides a formalisation of protocols in which processes are treated as resources and provides a framework for the analysis of indefinite causal structures. The second new perspective comes from the development of categorical quantum mechanics, which organises physical theories based on the background assumption that those theories always come with notions of transformations and their composition - in other words they form symmetric monoidal categories. In this talk, I will introduce monoidal categories and supermaps and discuss some key results and applications of both of these now-established perspectives. Next, I’ll discuss some motivations for putting them together and discuss the approaches we have recently used to do so, ultimately proposing a new formal definition of supermap for general theories of processes [1]. The main technical result I’ll discuss is a reconstruction of the standard definition of a supermap for both finite dimensional classical information theory, and for finite dimensional quantum information theory, derived from the proposed purely categorical (and physically well-motivated) definition. [1] Quantum Supermaps are Characterized by Locality: Matt Wilson, Giulio Chiribella, Aleks Kissinger
Seminaire : Séminaire DALGO : Maria Kokkou
17/10/2023 à 09h30
Titre: Stationary and Deterministic Leader Election for Programmable Matter in the Presence of ObstaclesRésumé : Programmable Matter refers to simple computational entities (here called particles) that are able to change their physical properties such as their shape, colour or texture in order to collaboratively accomplish a given task. In this talk, we consider the Leader Election problem which is often an intermediate step for the solution of more complex problems in the context of programmable matter. We consider the problem in the previously studied Amoebot model on a triangular grid, when the configuration is connected but contains obstacles (i.e., nodes the particles cannot move to) and holes (i.e., empty nodes, not occupied by particles or obstacles). We assume that particles only agree on one direction (i.e., the horizontal axis) but do not have chirality (i.e., they do not agree on the other two directions of the triangular grid). We prove that an election algorithm with explicit termination is not possible in this case, but we provide an implicitly terminating algorithm that elects a unique leader without requiring any movement. These results are in contrast to those in the more common model with chirality but no agreement on directions, where explicit termination is always possible but the number of elected leaders depends on the symmetry of the initial configuration. Solving the problem under the assumption of one common direction allows for a unique leader to be elected in a stationary and deterministic way, which until now was only possible under a sequential scheduler or assuming strongly connected configurations. In this talk, I will first show why an explicitly terminating leader election algorithm is not possible and then I will present our algorithm for deterministically electing a unique leader by stationary particles with constant memory. (Joint work with Jérémie Chalopin and Shantanu Das)
Seminaire : Séminaire CANA : Julian Wechs
10/10/2023 à 14h00
Où : Salle 04.05, bât TPR2, LuminyTitre: Subsystem decompositions of quantum circuits and processes with indefinite causal order
Résumé : One can theoretically conceive of situations in which the causal order between quantum operations is no longer well-defined. Such causally indefinite processes are of interest from a foundational perspective, but could also open up new possibilities in quantum information, as they go beyond the conventional paradigm of quantum circuits. A central question is which of these processes have an operational interpretation or physical realisation, and, more particularly, whether indefinite causal order could be realised within standard physics. It has been shown that certain causally indefinite processes can take place as part of standard quantum mechanical evolutions, described by acyclic quantum circuits, if the latter are represented with respect to an alternative choice of quantum subsystems that can be delocalised in time. In this seminar, I will present a general framework to describe such transformations between different subsystem decompositions of quantum circuits. This puts the notion that indefinite causal order is realisable in standard quantum theory on a rigorous footing. Based on Nat. Commun. 14, 1471 and work in preparation.
Seminaire : Séminaire ACRO : Oscar Defrain (09 octobre, 10h)
09/10/2023 à 10h00
Titre : Énumération Algorithmique III. Difficultés de l’énumération et réductions polynomiales. Résumé : Cet exposé est le troisième d’une série d’exposés sur le thème de l’énumération algorithmique où seront présentés différentes techniques, résultats et problèmes ouverts dans ce domaine relativement récent. Dans cet épisode, on s’intéressera aux réductions polynomiales entre problèmes d’énumération, et à la preuve de leur difficulté qui se traduit bien souvent par « il n’existe pas d’algorithme total-polynomial pour Π à moins que P = NP » et qui de fait exclut la possibilité d’algorithmes à délai polynomial ou incrémental polynomial. On s’intéressera en particulier aux problèmes d’énumération des indépendants maximaux donnés par un oracle, à l’énumération des modèles maximaux d’une formule de Horn, et à la place importante que s’est faite la dualisation des fonctions monotones Booléennes en énumération.Seminaire : Séminaire MoVe avec Benjamin Monmege
05/10/2023 à 10h30
Qui ? Benjamin Monmege Quand ? Jeudi 5/10 à 10h30 Où ? 4.05 TPR2 Campus Luminy et sur zoom si quelqu'un le demande, lien: https://univ-amu-fr.zoom.us/j/83571746230?pwd=QmY1OExPZHczb29ScGtRZ2E0TTBjdz09 Quoi ? An Automata Theoretic Characterization of Weighted First-Order Logic Mais encore ? Since the 1970s with the work of McNaughton, Papert and Schützenberger, a regular language is known to be definable in the first-order logic if and only if its syntactic monoid is aperiodic. This algebraic characterisation of a fundamental logical fragment has been extended in the quantitative case by Droste and Gastin, dealing with polynomially ambiguous weighted automata and a restricted fragment of weighted first-order logic. In the quantitative setting, the full weighted first-order logic (without the restriction that Droste and Gastin use, about the quantifier alternation) is more powerful than weighted automata, and extensions of the automata with two-way navigation, and pebbles or nested capabilities have been introduced to deal with it. In this work, we characterise the fragment of these extended weighted automata that recognise exactly the full weighted first-order logic, under the condition that automata are polynomially ambiguous.Rencontre : Le LIS à la Nuit Européenne des Chercheurs 2023
29/09/2023 à 18h00
Nous vous donnons rendez-vous ce vendredi 29 septembre de 18h à 23h30 aux Docks des Suds à Marseille pour la Nuit Européenne des Chercheurs, soirée festive et riche de culture scientifique grand public. Au sein du "Bureau de Désinformation", Valentin Emiya (LIS) et Anne Mathieu (INS) se risqueront à aborder la question "Les jeux vidéos peuvent-ils rendre intelligents?". Plus d'informations: http://url.univ-amu.fr/nuit-chercheurs-2023 .Conference :
28/09/2023 à 10h30
Qui ? Corto Mascle (doctorant à LaBri) Quand ? 28 septembre 10h30 Où ? 4.05 TPR2 Campus Luminy et sur zoom si quelqu'un le demande, lien: https://univ-amu-fr.zoom.us/j/83571746230?pwd=QmY1OExPZHczb29ScGtRZ2E0TTBjdz09 Quoi ? Reconfigurable broadcast networks with data. Mais encore ? Reconfigurable broadcast networks (RBN) are a well-studied model of distributed systems with arbitrarily many agents communicating by (unreliable) broadcast. In this talk we will study a version of RBN where agents have local registers. Register values are initially all distinct and may therefore be thought of as identifiers. When an agent broadcasts a message, it appends to it the value stored in one of its registers. Upon reception, an agent can store the received value or test this value for equality with one of its own registers. We consider the coverability problem (whether some state q may be reached by at least one agent) for this model. We establish that this problem is decidable, by reasoning about parallelism and transition systems with registers to be able to leverage well quasi-order theory. This is joint work with Lucie Guillou and Nicolas Waldburger.Seminaire : Séminaire ACRO : Guyslain Naves
25/09/2023 à 10h00
Titre : Plongement dans L1 de métriques planaires préservant les distances entre sommets d'une même face. Résumé : Le théorème d'Okamura-Seymour affirme que les métriques induites par un graphe planaire sur les sommets de sa face extérieure sont plongeables dans L1. Une conjecture fameuse est que toute métrique induite par un graphe planaire est plongeable dans L1 avec une distortion constante. Je présenterai un article récent de Nikhil Kumar (FOCS 2022) qui étend le théorème d'Okamura-Seymour et constitue une avancée vers cette conjecture : tout graphe planaire G est plongeable dans L1, de sorte que pour toute face F, la métrique induite sur cette face subit une distortion constante.Seminaire : Séminaire ACRO : Victor Chepoi
11/09/2023 à 10h00
Titre : Separation axioms S3 and S4 in convexity spaces and graphs. Résumé court : In the talk, we will present old and new results about the separation by halfspaces of pairs of disjoint convex sets (S4) and of points and convex sets (S3).WorkShop : Workshop on Management of Data under Uncertainty (MoDU 2023) @ADBIS 2023
04/09/2023 à 09h00
1st Workshop on Management of Data under Uncertainty (MoDU 2023) @ ADBIS 2023 Barcelona, Spain Website: https://modu2023.lis-lab.fr/ The aim of the workshop is to allow academics and industrial from various areas to share their experiences on management of uncertain data (Uncertainty in data collection and querying, Uncertainty in ML and Deep learning models, Uncertainty in data analytics). ** WORKSHOP ORGANIZERS ** • Richard Chbeir, University Pau & Pays Adour, Anglet, France • Allel Hadjali, Engineer School ENSMA, Poitiers, France • Sana Sellami, Aix Marseille University, Marseille, FranceSeminaire : Séminaire CANA : Kévin Perrot
11/07/2023 à 11h00
Titre : Une preuve du premier théorème d’incomplétude de Gödel avec la complexité de Kolmogorov Lieu : TPR2/04.05 (Luminy) Résumé : Je propose de tenter cette preuve, due à Chaitin. Elle repose sur une formalisation du paradoxe de Berry : soit l’expression « le plus petit entier positif qui n’est pas définissable en moins de seize mots ». Cette expression définit cet entier en moins de seize mots, ce qui est paradoxal. Pour celles et ceux qui ne connaissent rien aux théorèmes d’incomplétude de Gödel et/ou à la calculabilité, je recommande de visionner les deux vidéos suivantes pour vous échauffer (10 minutes chacune) : https://www.arte.tv/fr/videos/097454-007-A/voyages-au-pays-des-maths et https://www.arte.tv/fr/videos/097454-005-A/voyages-au-pays-des-maths/. Ce séminaire n’attend aucun pré-requis de son auditoire, on pourra discuter de tout (en particulier de ce que disent les énoncés des théorèmes d’incomplétude de Gödel) et j’espère bien que vous aurez des questions pour m’aider à savoir quoi vous raconter (sinon, pour la preuve en elle-même, en 5 minutes c’est plié…).Conference : Séminaire ACRO : Feodor Dragan (26 juin, 10h)
26/06/2023 à 10h00
Titre : α_i-Metric Graphs: Radius, Diameter and all Eccentricities Résumé : We extend known results on chordal graphs and distance-hereditary graphs to much larger graph classes by using only a common metric property of these graphs. Specifically, a graph is called α_i-metric (i∈\mathcal{N}) if it satisfies the following α_i-metric property for every vertices u,w,v and x: if a shortest path between u and w and a shortest path between x and v share a terminal edge vw, then d(u,x) ≥ d(u,v) + d(v,x) - i. Roughly, gluing together any two shortest paths along a common terminal edge may not necessarily result in a shortest path but yields a ``near-shortest'' path with defect at most i. It is known that α_0-metric graphs are exactly ptolemaic graphs, and that chordal graphs and distance-hereditary graphs are α_i-metric for i=1 and i=2, respectively. We show that an additive O(i)-approximation of the radius, of the diameter, and in fact of all vertex eccentricities of an α_i-metric graph can be computed in total linear time. Our strongest results are obtained for α_1-metric graphs, for which we prove that a central vertex can be computed in subquadratic time, and even better in linear time for so-called (α_1,Δ)-metric graphs (a superclass of chordal graphs and of plane triangulations with inner vertices of degree at least 7). The latter answers a question raised in (Dragan, IPL, 2020). Our algorithms follow from new results on centers and metric intervals of α_i-metric graphs. In particular, we prove that the diameter of the center is at most 3i+2 (at most 3, if i=1). The latter partly answers a question raised in (Yushmanov & Chepoi, Mathematical Problems in Cybernetics, 1991). This is a joint work with Guillaume Ducoffe.Seminaire : Séminaire/cours CANA : Enrico Formenti
20/06/2023 à 14h00
Orateur : Enrico Formenti (I3S)Lieu : TPR2/04.05 (Luminy)
Titre : Introduction aux séries formelles
Résumé : Les séries formelles (SFs) sont un outil fondamental dans l’analyse combinatoire mais aussi dans l’analyse complexe. Dans ce cours/séminaire nous chercherons à donner un petit aperçu du rôle joué par les SFs dans des contextes assez différents. Le cours est donc structuré en plusieurs parties. Dans cette première partie nous parlerons de récurrences (linéaires et non) et montrerons comment les SFs puissent (dans certains cas) aider à trouver les termes généraux de ces récurrences. Nous montrerons aussi à l’occasion des liens avec les systèmes dynamiques discrets.
Seminaire : Séminaire ACRO : Alixel Bagnis (19 juin, 10h)
19/06/2023 à 10h00
Titre : Énumération des signatures d'une CNF. Résumé : Si Φ = C1 ∧ C2 ∧ … ∧ Cm est une CNF et 𝓪 est un assignement, alors la signature de 𝓪 sur Φ est le mot binaire s où le i-ème bit est à 1 si et seulement si 𝓪 évalue Ci à 1. On appelle un mot binaire de taille m une signature de Φ s’il existe un assignement dont il est la signature sur Φ. La signature vient traduire le fait qu’il existe un assignement qui satisfait telles et telles clauses et ne satisfait pas telles ou telles clauses. En particulier Φ est satisfiable ssi 111…1 est une signature. De ce fait, décider si s est la signature d'une 3-CNF est NP-complet. Malgré tout et de façon assez étonnante, Berczi et al. montrent que l'énumération de toutes les signatures d'une CNF quelconque reste possible en temps incrémental polynomial. L'objet de cet exposé est de présenter le problème, l'algorithme de Berczi et al., et de distinguer quelques questions ouvertes qui ont été l'objet de ce stage.Seminaire : Demi Journées du Pôle Calcul
15/06/2023 à 09h30
Speaker : Liva Ralaivola (Criteo AI Lab)Title : Differentially-Private Sliced Wasserstein Distance
Absrtract : Developing machine learning methods that are privacy preserving is today a central topic of research, with huge practical impacts. Among the numerous ways to address privacy-preserving learning, we here take the perspective of computing the divergences between distributions under the Differential Privacy (DP) framework --- being able to compute divergences between distributions is pivotal for many machine learning problems, such as learning generative models or domain adaptation problems. Instead of resorting to the popular gradient-based sanitiziation method for DP, we tackle the problem at its roots by focusing on the Sliced Wasserstein Distance and seamlessly making it differentially private. Our main contribution is as follows: we analyze the property of adding a Gaussian perturbation to the intrinsic randomized mechanism of the Sliced Wasserstein Distance, and we establish the sensitivity of the resulting differentially private mechanism. One of our important finding is that this DP mechanism transforms the Sliced Wasserstein distance into another distance, that we call the Smoothed Sliced Wasserstein Distance. This new differentially-private distribution distance can be plugged into generative models and domain adaptation algorithms in a tranparent way, and we empirically show that it yields highly competitive performance compared with gradient-based DP approaches from the literature, with almost no loss in accuracy for the domain adaptation problems that we consider. (Joint work with A. Rakotomamonjy (Criteo AI Lab))
11:00 - 11:30
Speaker : Van-Giang Trinh (LIRICA, LIS)
Title: Efficient enumeration of fixed points in complex Boolean networks using answer set programming
Abstract: Boolean Networks (BNs) are an efficient modeling formalism with applications in various research fields such as mathematics, computer science, and more recently systems biology. One crucial problem in the BN research is to enumerate all fixed points, which has been proven crucial in the analysis and control of biological systems. Indeed, in that field, BNs originated from the pioneering work of R. Thomas on gene regulation and from the start were characterized by their asymptotic behavior: complex attractors and fixed points. The former being notably more difficult to compute exactly, and specific to certain biological systems, the computation of stable states (fixed points) has been the standard way to analyze those BNs for years. However, with the increase in model size and complexity of Boolean update functions, the existing methods for this problem show their limitations. To our knowledge, all the state-of-the-art methods for the fixed point enumeration problem rely on Answer Set Programming (ASP). Motivated by these facts, in this work we propose two new efficient ASP-based methods to solve this problem. We evaluate them on both real-world and pseudo-random models, showing that they vastly outperform four state-of-the-art methods as well as can handle very large and complex models.
https://demi-journees-pole-calcul.lis-lab.fr/
Seminaire : Séminaire ACRO : Oscar Defrain (12 juin, 10h)
12/06/2023 à 10h00
Titre : Minimal dominating sets enumeration with FPT-delay parameterized by the maximum degree Résumé : At STOC 2002, Eiter, Gottlob, and Makino presented a technique called ordered generation that yields an n^{O(d)}-delay algorithm listing all minimal transversals of an n-vertex hypergraph of degeneracy d, for an appropriate definition of degeneracy. Recently at IWOCA 2019, Conte, Kanté, Marino, and Uno asked whether, even for a more restrictive notion of degeneracy, this XP-delay algorithm parameterized by d could be improved to an FPT-delay algorithm parameterized by d and the maximum degree ∆, i.e., an algorithm with delay f(d, ∆) · n^{O(1)} for some computable function f. We answer this question in the affirmative whenever the hypergraph corresponds to the closed neighborhoods of a given graph, i.e., we show that the intimately related problem of enumerating minimal dominating sets in graphs can be solved with FPT-delay parameterized by the degeneracy and the maximum degree https://acro.lis-lab.fr/seminarsSeminaire : Séminaire MoVe avec Elli Anastasiadi
08/06/2023 à 10h30
ui ? Elli Anastasiadi (Uppsala University) Quand ? jeudi 8.6 à 10h30 Où ? 4.05 au TPR2 comme d'habitude, et en ligne sur demande (il faut demander) On pourra aussi suivre ca ensemble dans la salle usuelle 4.05 au TPR2. Quoi ? Verification of weak memory models Mais encore ? Distributed algorithms and architectures are everywhere, and along with them bring faster computation and harder verification. In the heart of the verification effort lies always the the understanding of how exactly a piece of software can execute, and it is exactly there where parallelism and concurrency introduce extra potential execution scenaria and complicate the process. The concept of weak memory approaches this issue from an applied perspective, where the implementation of a system is what defines what potential executions can occur. Unfortunately the outcome is usually that many, additional to the expected ones, program behaviours are present, and thus the program's safety is even more at risk. In this talk we will first look at exactly how weak memory presents itself through different implementations and then discuss some important concepts and problems about the verification of programs in those circumstances.Seminaire : Séminaire CANA : Van-Giang Trinh
30/05/2023 à 14h00
Orateur : Van-Giang Trinh (LIS)Lieu : TPR2/04.05 (Luminy)
Titre : Trap spaces of Boolean networks are conflict-free siphons of their Petri net encoding
Abstract : Boolean network modeling of gene regulation but also of post-transcriptomic systems has proven over the years that it can bring powerful analyses and corresponding insight to the many cases where precise biological data is not sufficiently available to build a detailed quantitative model. Besides simulation, the analysis of such models is mostly based on attractor computation, since those correspond roughly to observable biological phenotypes. The recent use of trap spaces made a real breakthrough in that field allowing to consider medium-sized models that used to be out of reach. However, with the continuing increase in model size and complexity of Boolean update functions, the state-of-the-art computation of minimal trap spaces based on prime-implicants shows its limits due to the difficulty of the prime-implicant computation.
In this article we explore and prove for the first time a connection between trap spaces of a general Boolean network and siphons of its Petri net encoding. Besides important theoretical applications in studying properties of trap spaces, the connection enables us to propose an alternative approach to compute minimal trap spaces, and hence complex attractors, of a general Boolean network. It replaces the need for prime-implicants by a completely different technique, namely the enumeration of maximal siphons in the Petri net encoding of the original model. We then demonstrate its efficiency and compare it to the state-of-the-art methods on a large collection of real-world and randomly generated models.
Conference : ORASIS 2023
22/05/2023 à 00h00
La 19ième édition du colloque d’ORASIS, journées francophones des jeunes chercheurs en vision par ordinateur, se déroulera du 22 au 26 mai 2023 à Carqueiranne (Var, PACA). Elle sera organisée par l'équipe Signal et Image du Laboratoire d'Informatique et Systèmes UMR7020, au centre vacanciel Miléade à Carqueiranne. Ce colloque vise à réunir de jeunes chercheurs francophones (doctorants et jeunes docteurs) issus de la communauté de la vision par ordinateur ou de domaines connexes, avec l'ambition de favoriser, dans une ambiance conviviale, les échanges entre les participants, notamment entre les jeunes chercheurs et chercheurs expérimentés dans le domaine. Les journées seront rythmées par des sessions plénières ainsi que des sessions posters. Plusieurs sessions (7) de conférenciers invités complètent le déroulement de ces journées. Plus d'informations et soumissions: https://orasis2023.sciencesconf.org/Seminaire : Séminaire ACRO : Guyslain Naves (15 mai, 4.05 10h)
15/05/2023 à 10h00
Titre : Répartiteur dans les réseaux de convoyeurs Résumé : Lors d'un précédent exposé, j'avais introduit les réseaux de convoyeurs, modélisant le transport de matériaux sur des tapis roulants et utilisant des appareils nommés splitters et permettant d'uniformiser les charges entre deux tapis. Dans cet exposé, après un rappel des notions, je montrerais comment construire des réseaux permettant d'uniformiser les charges d'un nombre arbitraire de tapis avec aussi peu de splitters que possible. Je prouverai des bornes inférieures sur le nombre de splitters nécessaires, et selon le temps aborderai quelques résultats supplémentaires de complexité. Il n'est pas nécessaire d'avoir vu l'exposé précédent pour suivre celui-ci.Seminaire : Séminaire I&M - Adrien JULIA
12/05/2023 à 14h00
Titre :Post-processings of Light Sheet Fluorescence Microscope Images using autoencoders and Richardson-Lucy deconvolutionLieu : Luminy, TPR2 salle de réunion 04.03.
Résumé :
Light Sheet Fluorescence Microscopy is useful for neurobiologists but may induce artifacts on reconstructed 3D volumes. A three-step pipeline is proposed to improve the quality of slice-by-slice images. It includes a 2D deconvolution algorithm, automatic contrast enhancement, and a convolutional denoising autoencoder to remove noise. Additionally, a new approach is proposed to solve the axial distortion problem using an autoencoder trained on calibration bead images. This pipeline enhances the understanding of biological images by surpassing existing methods.
Seminaire : Séminaire CANA : Eurico Ruivo
02/05/2023 à 14h00
Orateur : Eurico Ruivo (Universidade Presbiteriana Mackenzie, Brazil) Lieu : TPR2/04.05 (Luminy)Titre : An asynchronous solution to the synchronisation problem for binary one-dimensional cellular automata Abstract: Because cellular automata rely on totally local and synchronous processing at the neighbourhood of each cell, the issue of global synchronisation of the cell states has a long tradition in cellular automata literature. In order to solve the synchronisation problem in periodic boundary condition, a rule needs to be conceived so as to lead any initial configuration to converge to a cyclic regime of period 2 characterised by all cells alternating between fully homogeneous configurations of 0s and 1s. In spite of its simplicity, the problem has been shown not to have a solution by synchronously updating the cell states. In contrast, we provide a solution to the problem, with a 4-neighbour rule, by replacing the synchronous update of the cells of the lattice with a deterministic, block sequential asynchronous update schedule.
Seminaire : Séminaire ACRO : Mathieu Mari (17 avril, REU 04.05, 10h)
17/04/2023 à 10h00
Orateur : Mathieu Mari (MIMUW, Université de Varsovie). Titre : A (2+ɛ)-Approximation Algorithm for Maximum Independent Set of Rectangles. Résumé : We study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overlapping rectangles of maximum cardinality. In a recent breakthrough, Mitchell obtained the first constant-factor approximation algorithm for MISR. His algorithm achieves an approximation ratio of 10 and it is based on a dynamic program that intuitively recursively partitions the input plane into special polygons called corner-clipped rectangles (CCRs), without intersecting certain special horizontal line segments called fences. In this talk, I will present a (2+ɛ)-approximation algorithm for MISR which is also based on a recursive partitioning scheme. First, we use a partition into a class of axis-parallel polygons with constant complexity each that are more general than CCRs. This allows us to provide an arguably simpler analysis and at the same time already improves the approximation ratio to 4. Then, using a more elaborate charging scheme and a recursive partitioning into general axis-parallel polygons with constant complexity, we improve our approximation ratio to 2+ɛ. In particular, we construct a recursive partitioning based on more general fences which can be sequences of up to O(1/ɛ) line segments each. This partitioning routine and our other new ideas may be useful for future work towards a PTAS for MISR. At the end of the talk, I will present a bunch of future research directions related to the problem. This is a joint work with Waldo Gálvez, Arindam Khan, Tobias Mömke, Madhusudhan Reddy and Andreas Wiese.Seminaire : Séminaire ACRO : Colin Geniet
12/04/2023 à 00h00
Titre : Twin-width of groups and bounded degree graphs Résumé : Twin-width is a graph invariant introduced by Bonnet, Kim, Thomassé, and Watrigant, with notable applications in logic, FPT algorithms, and graph coloring. When considering graphs of bounded degree, finiteness of twin-width is stable under quasi-isometries, and thus it defines an invariant of the Cayley graphs of a group. For a group G, having finite twin-width is equivalent to admitting a total order for which the self-action by product avoids some permutations as patterns, which makes twin-width a far reaching generalisation of the notion of orderable groups. Several well-known classes of groups have finite twin-width: abelian groups, solvable groups, groups with polynomial growth, and hyperbolic groups. On the other hand, the class of all cubic graphs is known to have unbounded twin-width by a counting arguments: for any k, there are only n!c^n graphs of twin-width k on vertices {1,...,n} for some constant c (we say that it is a _small_ class of graphs), which is asymptotically less than the number of cubic graphs. Using an embedding theorem of Osajda, we adapt this construction to prove that there are groups with infinite twin-width. The Cayley graphs of such groups induce classes of graphs which are small but have unbounded twin-width, answering a question from previous works. Unfortunately, because these constructions are enumerative and probabilistic, it is essentially impossible to understand the resulting group. Finding an explicit construction for graphs with bounded degree (or groups) and unbounded twin-width remains a major open problem. This is joint work with Édouard Bonnet, Romain Tessera, and Stéphan Thomassé.Seminaire : Séminaire ACRO : Clément Dallard
03/04/2023 à 10h00
Titre : Introduction to tree-independence number Résumé : Tree decompositions are a common and useful data structure for designing dynamic programming algorithms for graph problems. In order to obtain efficient algorithms, one looks for a tree decomposition of the input graph that minimizes some measure on the subgraphs induced by the bags. For instance, when this measure is the number of vertices, we obtain the well-known notion of treewidth. In this talk, the considered measure is the independence number. The independence number of a tree decomposition of a graph G is the smallest integer k such that each bag induces a subgraph with independence number at most k. The tree-independence number of G is defined as the minimum independence number over all tree decompositions of G. Given a tree decomposition with bounded independence number, the Maximum Weight Independent Set and several related NP-hard problems can be solved in polynomial time. We will discuss how to compute tree decompositions with bounded independence number efficiently (when they exist), the algorithmic use of such tree decompositions, and the strong relationship with the notion of (tw,ω)-boundedness.Seminaire : Séminaire I&M - Sabrine djedjiga OUCHERIF
31/03/2023 à 14h00
Titre :Apports d’un système de vision plénoptique pour l’analyse des comportements.Lieu : Luminy, TPR2 salle de réunion 04.03.
Résumé :
Durant les quatre dernières décennies, le problème de l’analyse du comportement a été largement étudié dans la communauté scientifique. L’étude de la reconnaissance des expressions faciales représente l’approche la plus abordée qui permet de traiter et d’analyser le comportement humain à travers ses émotions.
Le Centre d’Étude et de Recherche en Gestion d’Aix Marseille (CERGAM) en collaboration avec le Laboratoire d’Informatique et Systèmes(LIS) et l’Institut de Mathématiques de Marseille (I2M) aspirent à développer les recherches de l’analyse comportementale dans le domaine du marketing en exploitant les performances des caméras plénoptiques[1, 2].Ce système de vision, appelé également photographie en champ lumineux(en anglais: light field (LF)camera), permet d’acquérir des informations sur l’intensité et la direction d’arrivée des rayons lumineux. De ce fait, nous pouvons obtenir des images représentant différents points de vue de la même scène en une seule prise et construire une carte de profondeur.
L’objectif de ce projet est d’étudier et d’analyser le comportement des personnes dans une surface de vente. Pour y parvenir, nous nous intéresserons d’un coté à l’analyse et la reconnaissance des expressions faciales, et de l’autre, à l’estimation de la position du regard à partir des informations renvoyées par les caméras plénoptiques. Concernant le premier point, différentes architectures de réseaux de neurones seront développées afin de traiter les informations renvoyées par les images LF.
[1] T. -W. Shenet al., "Facial expression recognition using depth map estimation of Light Field Camera,"2016 IEEE International Conference on Signal Processing, Communications and Computing(ICSPCC), 2016, pp.1-4, doi: 10.1109/ICSPCC.2016.7753695.
[2] A. Sepas-Moghaddam, A. Etemad, F. Pereira and P. L. Correia, "Facial Emotion Recognition Using Light Field Images with Deep Attention-Based Bidirectional LSTM," ICASSP 2020 -2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2020, pp. 3367-3371, doi: 10.1109/ICASSP40776.2020.9053919.
Seminaire : Séminaire pôle ACS - David Hill
30/03/2023 à 14h00
Titre : Reproductibilité et répétabilité des simulations stochastiques Résumé : L'un des critères majeurs de la scientificité d'une étude de recherche est la reproductibilité. Dans cet exposé, nous présenterons les principales définitions autour de la reproductibilité, elles ont évolué récemment à l’ACM en 2020. Nous examinerons dans quelle mesure les travaux d'informatique et de simulation sont concernés. Nous donnerons quelques exemples d'applications incluant des simulations stochastiques parallèles, qui sont trop souvent présentées comme non reproductibles. Toute personne souhaitant produire un travail scientifique en simulation a intérêt à prêter attention à la reproductibilité numérique de ses résultats. Des différences significatives peuvent être observées dans les résultats de simulations parallèles si les meilleures pratiques ne sont pas appliquées. Nous verrons que même dans ce contexte, il est possible de reproduire les mêmes résultats numériques en mettant en œuvre une méthode rigoureuse testée jusqu'à un milliard de threads. Il est ainsi possible de vérifier les résultats parallèles avec leurs contreparties séquentielles et ce avant un passage « à l'échelle », gagnant ainsi en confiance dans les modèles développés. Ce séminaire présentera quelques bonnes pratiques pour des simulations stochastiques parallèles, permettant même de faire face erreurs silencieuses qui impactent les supercalculateurs (dont la machine Exascale présentée l’an passé à Hambourg).Seminaire : Séminaire ACRO : Benjamin Bergougnoux
27/03/2023 à 00h00
Titre : A logic-based algorithmic meta-theorem for mim-width Résumé : We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints (𝖠&𝖢 𝖣𝖭 for short) which extends existential 𝖬𝖲𝖮𝟣 with predicates for querying neighborhoods of vertex sets and for verifying connectivity and acyclicity of vertex sets in various powers of a graph. Building upon [Bergougnoux and Kanté, ESA 2019; SIDMA 2021], we show that the model checking problem for every fixed 𝖠&𝖢 𝖣𝖭 formula is solvable in n^O(w) time when the input graph is given together with a branch decomposition of mim-width w. Nearly all problems that are known to be solvable in polynomial time given a branch decomposition of constant mim-width can be expressed in this framework. We add several natural problems to this list, including problems asking for diverse sets of solutions. Our model checking algorithm is efficient whenever the given branch decomposition of the input graph has small index in terms of the d-neighborhood equivalence [Bui-Xuan, Telle, and Vatshelle, TCS 2013]. We therefore unify and extend known algorithms for tree-width, clique-width and rank-width. Our algorithm has a single-exponential dependence on these three width measures and asymptotically matches run times of the fastest known algorithms for several problems. This results in algorithms with tight run times under the Exponential Time Hypothesis (𝖤𝖳𝖧) for tree-width and clique-width; the above mentioned run time for mim-width is nearly tight under the 𝖤𝖳𝖧 for several problems as well. Our results are also tight in terms of the expressive power of the logic: we show that already slight extensions of our logic make the model checking problem para-𝖭𝖯-hard when parameterized by mim-width plus formula length.Rencontre : PhDays'2023 du LIS
22/03/2023 à 09h00
(English version bellow)La journée des doctorante du LIS aura lieu le mercredi 22 mars 2023 à Luminy, dans amphithéâtre de l'Hexagone (nouvelle BU).
La participation est gratuite, sur inscription. Pour cela vous pouvez remplir le framacalc reçu par courriel, ou bien informer directement par email l'un.e des organisateur.trice. Une courte présentation de votre travail (seul ou en groupe) d'environ 10 minutes par personne, serait grandement appréciée !
Le programme (très) provisoire de la journée sera composé le matin de sessions de présentation entrecoupées d'une pause café, le repas de midi est offert aux participants, puis l'après-midi des activités sportives/sociales seront proposées pour profiter du cadre de Luminy !
Si vous avez des propositions ou remarques, n'hésitez pas à nous contacter.
Merci d'avance pour vos retours,
Elie Antoine, Alexandre Coppé, Raphael Gass, Emmanuelle Salin, Kévin Perrot
--
The PhD student day of the LIS will take place on Wednesday 22nd March 2023 at Luminy, in the amphitheatre of the Hexagone building (new library).
Paticipation is free, but registration is required. For this you can fill the framacalc received by email, or inform directly by email one of the organizers. A short presentation of your work (alone or by group) of around 10 minutes would be much appreciated!
The (very) provisional program of the day will be composed of scientific sessions in the morning, with coffee break, then a lunch offered to the participants, and during the afternoon some social/sport activities to enjoy the Luminy campus!
If you have any question or remark, feel free to contact us.
Thanks in advance for your participation,
Elie Antoine, Alexandre Coppé, Raphael Gass, Emmanuelle Salin, Kévin Perrot
Seminaire : Séminaire ACRO : Jean-Florent Raymond (20 mars, 10h)
20/03/2023 à 10h00
Titre : A lower bound for constant-size local certification Résumé : Given a graph property, a local certification is a labeling that allows to locally check that the property is satisfied. The quality of a certification is measured by the size of its labels: the smaller, the better. This can be seen as a measure of the locality of a property (where properties that can be certified with "small" labels are considered more local than the others). An active line of research is to identify the optimal label size for a given graph property. It turns out that properties can be classified into three important regimes: the properties for which the optimal size is polynomial in the number of vertices of the graph, the ones that require only polylogarithmic size, and the ones that can be certified with a constant number of bits. The first two regimes are well studied, with several upper and lower bounds, specific techniques, and active research questions. On the other hand, the constant regime has never been really explored, at least on the lower bound side. In this talk I will present the first non-trivial lower bound for this low regime: k-colorabilty cannot be certified with just one bit.Seminaire : Séminaire MoVe avec K.S. Chana Weil-Kennedy
16/03/2023 à 10h30
Title : Observation Petri Nets Abstract : Petri nets are a classic formal model for concurrent systems, extensively studied and used since the 1970s. They model fundamental features of concurrent systems such as synchronization, process creation, and choice. Many subclasses of Petri nets have been defined by forbidding one or more of these features (e.g. T-systems, free-choice nets, communication-free nets). In our work, we introduce a feature of Petri nets called observation, which is a restricted form of synchronization. We give a syntactic definition of a class of Petri nets in which the only possible form of synchronization is observation. We study the complexity of analysis problems for this class, called observation Petri nets, and in particular we consider verification problems parameterized by the number of tokens (or processes) in the Petri net. The main analysis problems we study are the class of generalized reachability problems. This class extends reachability queries to possibly infinite sets of markings (or configurations). It includes the cube-reachability problem, which given two sets asks if there is a marking in the first set which can reach a marking in the second set. We show that this class of problems can be decided in polynomial space for observation Petri nets. The classic reachability problem asking if a marking can reach another is also in polynomial space for our observation Petri nets (versus non primitive recursive for general Petri nets). So our results show that it is not harder to check reachability between single markings than it is to check reachability between possibly infinite sets of markings. Thus the observation feature captures a non-trivial property of Petri nets that is particularly interesting for parameterized verification.Seminaire : Séminaire ACRO : Laurent Viennot
13/03/2023 à 10h00
Title : Temporalisation of walks/edges in a graph. Abstract : In a temporal graph, each edge appears and can be traversed at specific points in time. In such a graph, temporal reachability of one node from another is naturally captured by the existence of a temporal path where edges appear in chronological order. Inspired by the optimisation of bus/metro/tramway schedules in a public transport network, we consider the problem of turning a collection of walks (called trips) in a directed graph into a temporal graph by assigning a starting time to each trip so as to maximise the reachability among pairs of nodes. Each trip represents the trajectory of a vehicle and its edges must be scheduled one right after another. Setting a starting time to the trip thus forces the appearing time of all its edges. We call such a starting time assignment a trip temporalisation. We obtain several results about the complexity of maximising reachability via trip temporalisation. Among them, we show that maximising reachability via trip temporalisation is hard to approximate within a factor $\sqrt{n}/12$ in an $n$-vertex digraph, even if we assume that for each pair of nodes, there exists a trip temporalisation connecting them. On the positive side, we show that there must exist a trip temporalisation connecting a constant fraction of all pairs if we additionally assume symmetry, that is, when the collection of trips to be scheduled is such that, for each trip, there is a symmetric trip visiting the same nodes in reverse order. We will also discuss the basic problem of assigning times to the edges of a directed graphs so as to maximise temporal reachability.Seminaire : Séminaire ACRO : Valentin Bartier
06/03/2023 à 10h00
Titre : Reconfiguration d’ensembles indépendants dans les graphes peu denses • Résumé : Le problème de reconfiguration d’ensembles indépendants appartient au domaine plus large des problèmes de reconfiguration combinatoire. Il se formule de la manière suivante : étant donné une collection de jetons placés sur les sommets d’un ensemble indépendant d’un graphe, est-il possible de déplacer un à un ces jetons vers un autre ensemble indépendant cible, de telle sorte que deux jetons ne soient jamais voisins tout au long de la transformation ? Après une introduction générale sur la reconfiguration combinatoire et sur le problème de reconfiguration d’ensembles indépendants, nous nous concentrerons sur la variante du « Token Sliding ». Dans cette variante, une étape de la transformation consiste à déplacer un jeton d’un sommet vers un sommet voisin. Nous nous intéresserons plus particulièrement à la complexité paramétrée de ce problème dans des classes de graphes peu denses et aux nouveaux outils que nous avons récemment développé pour l’élaboration d’algorithmes FPT.Seminaire : Développement de systèmes multi-agents et application en environnement
02/03/2023 à 14h00
Le thème est la simulation de dynamiques urbaines (bidonvilles) par SMA (Système Multi-Agents) avec en arrière-plan des questions d’apprentissage supervisé des agents. L’un des enjeux est d’avoir des modèles explicables aux experts et permettant d’intégrer leur connaissance. Ce travail a lieu dans le cadre d’une convention CIFRE avec une entreprise calédonienne et s’inscrit dans le projet ANR SITI porté par F. Flouvat (équipe DANA).Conférencier : Etienne Tack (doctorant 2A, Insight & Univ Nouvelle Calédonie).
Lieu : LIS St Jérôme (Bat. Polytech).
Salle : Salle de Réunion Nord (Salle de réunion au 1er étage nord).
Lien Zoom : https://univ-amu-fr.zoom.us/j/84340041505?pwd=b0tudEpwYVJkSTA5ZHQwS3BJT2czdz09
Seminaire : Séminaire ACRO : Owen Rouillé (INRIA, Paris)
13/02/2023 à 10h00
Le prochain séminaire de l'équipe ACRO sera donné par Owen Rouillé (INRIA, Paris) qui nous parlera de l'utilisation de l'ordinateur pour aider à formuler ou prouver des conjectures mathématiques, notamment en géométrie. Titre : Experimenting in mathematics: examples of data generation and visualisation Résumé : Mathematics include many complex objects which are difficult to understand. In particular, intuition is crucial in teaching and research, allowing to state and prove conjectures. Building this intuition requires looking at and analysing many examples. Computers are very important tools at our disposal: they allow to generate and analyse large quantities of data, and visualise patterns that would be difficult to draw by hand. However, using them is not straightforward, and implementation raises many new questions, among which the encoding and the performances for instances. The talk is dedicated to the use of computers to help with mathematics. First, I will present part of the work I did during my PhD concerning the computation of two topological invariants for 3-manifolds (Turaev--Viro invariants and hyperbolic volume). These projects illustrate the use of computers in mathematics in a domain where the computations can be difficult and the datasets very large. Then, I will present the main project of my postdoc: the computation and the representation of limit sets in S^3, with a focus on triangular groups.WorkShop : Journées Revêtements
13/02/2023 à 00h00
Les premières Journées Marseillaises des Revêtements auront lieu à Marseille les 13 et 14 février 2023. Ce premier événement se concentrera sur l'utilisation des revêtements de graphes et de leurs généralisations pour l'étude des réseaux anonymes.
Objectifs des Journées
Les revêtements de graphes, et leurs généralisations, ont été introduits et utilisés par Angluin en 1980 pour étudier des problèmes de calcul distribué dans les réseaux anonymes. Les travaux des années 90 et du début des années 2000 (Yamashita et Kameda ; Boldi et Vigna ; Métivier et al) ont démontré l'utilité de ces outils pour produire les résultats les plus généraux, c'est à dire incluant les réseaux anonymes et non anonymes. Les recouvrements de graphes sont encore utilisés aujourd'hui pour étudier de nouveaux modèles de calculs. L'objectif de cet atelier est de faire le lien entre d'anciens résultats, parfois un peu oubliés, et de nouveaux modèles de calcul, et des résultats récents. Il s'agit d'un premier session d'une future série. C'est pourquoi l'accent est mis principalement sur les réseaux anonymes.Programme
Les matinées seront consacrées à des keynotes sur l'utilisation des couvertures de graphes pour les réseaux anonymes et les après-midi à des présentations de résultats récents utilisant, directement ou indirectement, les couvertures de graphes dans algorithmes distribués. Appel à témoignages : Une session spécifique sera dédiée aux témoignages concernant l’utilisation, ou la tentative d’utilisation, des revêtements de graphes. Il sera également possible de présenter des problèmes ouverts. Informations et inscription : https://coverings.lis-lab.fr Contact: coverings@lis-lab.frSeminaire : Séminaire modèles de langage - ChatGPT
09/02/2023 à 13h00
Le jeudi 09/02 à 13h, l'équipe TALEP a le plaisir d'accueillir, pour son séminaire, Géraldine Damnati de Orange Innovation.Sa présentation est intitulée : Premières évaluations et nouveaux use-cases, quelles limitations et quelles opportunités pour les Large Language Models en contexte opérationnel ?
Cette intervention sera précédée d'une introduction rapide de Benoit Favre sur les modèles et méthodes de TAL sur lesquelles repose ChatGPT. À la suite du séminaire, nous vous proposons d'avoir une discussion sur l'impact de cette technologie dans le cadre de nos enseignements.
Nous invitons l'ensemble des membres du LIS à participer à cet événement. Le séminaire aura lieu à l'amphi de l'Hexagone le jeudi 09/02 à 13h. Il sera possible d'y assister par zoom via le lien ci-dessous :
https://univ-amu-fr.zoom.us/j/86852094022?pwd=YVBvNVk0WlYwZ2hUS0VQcVozZnBVQT09
Ne manquez pas cette occasion unique de découvrir les dernières avancées en matière de technologies linguistiques !
Amicalement,
Carlos Ramisch
P.S. : ce message a été écrit à l'aide de ChatGPT, bien entendu.
Seminaire : Séminaire du pôle ACS
19/01/2023 à 11h00
Térence Bayen (LMA, Avignon) "A hybrid maximum principle including regional switching parameters." salle X133, campus de ToulonSeminaire : Séminaire pôle Signal & Image - Emmanuelle SALIN
16/12/2022 à 10h00
Titre :Vision-Language Transformer Models.Lieu : Luminy, TPR2 salle de réunion 04.02.
Résumé :
Vision-Language models combine information from the textual and visual modalities to extract multimodal representations. These models can be used as basis for a large range of multimodal vision-language tasks. The use of large pre-trained models based on the transformer architecture, inspired by recent advances in Natural Language Processing, have enabled great improvement on those tasks. However, their ability to understand complex multimodal concepts remains limited.
In this presentation, I will give an overview of vision-language transformer models: the different models and pre-training methods, how to evaluate them, their strengths and weaknesses and current trends of research.
Seminaire : Séminaire CANA : Jean-Marc Ginoux
13/12/2022 à 14h00
Orateur : Jean-Marc Ginoux (Institut Jules Verne, Université de Toulon)Lieu : TPR2/04.05 (Luminy)
Titre : Contextuality in composite systems: entanglement vs. the Kochen-Specker theorem
Abstract : Slow–fast dynamical systems, i.e. singularly or nonsingularly perturbed dynamical systems possess slow invariant manifolds on which trajectories evolve slowly. Since the last century various methods have been developed for approximating their equations. This talk aims, on the one hand, to propose a classification of the most important of them into two great categories: singular perturbation-based methods and curvature-based methods, and on the other hand, to prove the equivalence between any methods belonging to the same category and between the two categories. Then, a deep analysis and comparison between each of these methods enable to state the efficiency of the Flow Curvature Method which is exemplified with paradigmatic Van der Pol singularly perturbed dynamical system and Lorenz slow–fast dynamical system.
In his famous book entitled Theory of Oscillations, Nicolas Minorsky wrote: “each time the system absorbs energy the curvature of its trajectory decreases and vice versa”. By using the Flow Curvature Method, we establish that, in the ε-vicinity of the slow invariant manifold of generalized Liénard systems, the curvature of trajectory curve increases while the energy of such systems decreases. Hence, we prove Minorsky’s statement for the generalized Liénard systems. These results are then illustrated with the classical Van der Pol and generalized Liénard singularly perturbed systems.
References
Ginoux J.-M., 2021, “Slow Invariant Manifolds of Slow-Fast Dynamical Systems,” International Journal of Bifurcation and Chaos, Vol. 31(7) 2150112 (17 pages), 2021.
Ginoux J.-M., Lebiedz D., Meucci R. & Llibre J., 2022, “Flow curvature manifold and energy of generalized Liénard systems,” Chaos Solitons & Fractals, 161, 112354 (7 pages), 2022.
Seminaire : Séminaire G-MOD - Contribution à la génération stochastique d'apparences procédurales
02/12/2022 à 10h00
Invité : Guillaume Gilet (Université de Sherbrooke)
Salle : 5.37Zoom : https://univ-amu-fr.zoom.us/j/84432888361?pwd=NmNFSFRLRnZic2svK3d1SUZlQ1dTZz09
Titre : Contribution à la génération stochastique d'apparences procédurales
Résumé :Alors qu’existe une demande croissante pour des mondes virtuels visuellement riches et d’une taille tendant vers l’infini, la majeure partie du secteur industriel (notamment vidéo-ludique) repose essentiellement sur la création manuelle, par des infographistes, d’objets tridimensionnels à l’apparence complexe et détaillée. Cela impose de fait une limite sur la taille, la complexité et la richesse visuelle des mondes virtuels qu’il est possible d’observer, car chaque élément d’une scène a été conçu et placé « manuellement », ce qui engendre de nombreux problèmes, tels que le coût (financier et en main d’œuvre), le stockage et transfert de ces informations de grande taille, l’augmentation de la puissance de calcul requise pour manipuler ces scènes…Une alternative naturelle consiste alors à générer des objets virtuels et leurs apparences de manière procédurale, c’est-à-dire de manière automatique à l'aide de définitions et règles reposant sur des outils mathématiques et physiques. Nous nous focaliserons dans cet exposé sur la génération procédurale de l’apparence des objets virtuels, dont la difficulté majeure reste le choix des modèles et paramètres à utiliser : Quels modèles possèdent les « bonnes » propriétés ? Quels sont les paramètres et modèles suffisamment intuitifs pour offrir à la fois un contrôle facile sur le résultat final et une grande qualité visuelle ? Les surfaces visuellement riches exhibent une apparence complexe et variée, résultant, dans le monde réel, d’un ensemble de phénomènes physiques, chimiques, biologiques et d’interactions humaines. Alors que la modélisation et la simulation directe de ces phénomènes ne sont pas envisageables (dans le cadre temps-réel), l'utilisation de l'aléatoire dans les définitions procédurales permet d'accroître la variété des apparences générées. Toutefois, le contrôle de cet aléatoire est un problème difficile : où introduire l’aléatoire ? Qu’est ce qui doit être aléatoire ? Comment s’assurer de la qualité du résultat ? Nous présenterons dans cet exposé un ensemble de travaux et réflexions sur la pertinence de ce modèle aléatoire et tenterons d'apporter des éléments de réponses à la génération procédurale d'apparences complexes en temps réel.
Venez nombreux !
Seminaire : Séminaire I&M (Signal-Image) - Jules Collenne
25/11/2022 à 14h00
Titre :Aide au diagnostic du mélanome: approche par apprentissage de similarités.Lieu : Luminy, TPR2 salle de réunion 04.02.
Résumé :
Le mélanome est un cancer cutané de plus en plus fréquent dans les pays développés qui se distingue par sacapacité à métastaser très rapidement. Pour réduire la mortalité, une étape majeure est son diagnostic.Traditionnellement réalisé par les dermatologues, l’automatisation de cette étape pourrait permettre une meilleureprise en charge des patients, ainsi qu’un plus grand nombre de personnes analysées, notamment dans les zonesoù les dermatologues manquent. L’objectif de la thèse est donc d’imaginer et de réaliser de nouvelles manières dediagnostiquer le mélanome à l’aide de l’intelligence artificielle.
Alors que de nombreux travaux existent déjà dans le domaine du diagnostic du mélanome (comme l’usage deréseaux de neurones convolutifs simples), notre approche se concentre sur le concept du «vilain petit canard»[1],qui pourrait permettre un meilleur diagnostic. Contrairement aux approches précédentes se basant uniquementsur l’aspect visuel des lésions étudiées une à une, ce concept vise à comparer les lésions d’un même patient entreelles, de sorte à ce que les lésions différentes des autres aient une plus grande probabilité d’être des cancers de lapeau. Une telle information pourrait permettre un meilleur diagnostic ainsi qu’une meilleure compréhension, pourles dermatologues, des résultats donnés par les modèles de prédiction.
Plusieurs types de réseaux de neurones sont étudiés, notamment les réseaux de neurones siamois[2-4], ainsi que plusieurs algorithmes de détection d’anomalies et de clustering. Des expériences ont été menées afin d’analyser les performances de chaque modèle utilisé pour le diagnostic du mélanome.
Bibliographie :
[1] Grob JJ, Bonerandi JJ. The 'ugly duckling' sign: identification of the common characteristics of nevi in an individual as a basis for melanoma screening. Arch Dermatol. 1998 Jan;134(1):103-4. doi: 10.1001/archderm.134.1.103-a. PMID: 9449921.
[2] Xinlei Chen and Kaiming He. Exploring Simple Siamese Representation Learning. 2020.
[3] Xiao Wang et al. On the Importance of Asymmetry for Siamese Representation Learning.
[4] Kaiming He et al. Momentum Contrast for Unsupervised Visual Representation Learning. 2019.
Conference : International Conference on Systems and Control - ICSC'22
23/11/2022 à 00h00
L'«International Conference on Systems and Control» a lieu annuellement dans différents pays méditerranéens : Maroc (2012), Algérie (2013), Tunisie (2014), France (2021), etc. En 2022, le laboratoire LIS a pris en charge l’organisation de sa dixième édition qui se déroulera du 23 au 25 novembre. ICSC’22 réunira plus de 150 chercheurs. Elle représente un événement important pour l’échange et pour la communication des travaux scientifiques dans le domaine des sciences industrielles de l’ingénieur, et plus précisément de « l’automatique », connu dans le monde industriel comme le «contrôle/commande des systèmes».Conference : Séminaire CANA : Victor Lutfalla
22/11/2022 à 14h00
Orateur: Victor Lutfalla (GREYC, Caen)Lieu : TPR2/04.05 (Luminy)
Titre : Le problème du domino sur les sous-shifts de pavages par losanges
Abstract : Un pavage est un recouvrement du plan par des tuiles qui ne se chevauchent pas. On appelle sous-shift un ensemble de pavages qui est invariant par translation et fermé (pour la topologie habituelle sur les pavages).
Ici on s'intéresse au cas où il y a un nombre fini de tuiles à translation près, les tuiles sont des losanges, et à chaque fois que deux tuiles sont adjacentes elle partagent soit un unique sommet en commun soit une arête entière en commun.
Sur ces pavages, on peut imposer des règles locales (à la manière des tuiles de Wang) en ajoutant des couleurs sur les arêtes des tuiles avec la règle que deux tuiles qui partagent une arête doivent avoir la même couleur pour cette arête. Dans ce cas, pour une même tuile géométrique, on peut avoir plusieurs copies avec des couleurs différentes sur les arêtes.
Étant donné un sous-shift X de pavages par losanges, le problème du domino sur X prend en entrée un ensemble de règles locales F et renvoie Vrai si il existe un pavage de X qui respecte les règles locales F et Faux dans le cas contraire. Ce problème est indécidable et nous allons présenter une réduction du problème du domino sur un sous-shift de pavages par losanges depuis le problème du domino classique sur les tuiles de Wang.
Seminaire : Séminaire CANA : Étienne Miquey
15/11/2022 à 14h00
Orateur : Étienne Miquey (I2M)Lieu : TPR2/04.05 (Luminy)
Titre : Curry-Howard: unveiling the computational content of proofs
Abstract : This talk is meant to be an introduction talk on the Curry-Howard correspondence between proofs and programs, for people that may not be dreaming about the λ-calculus every night. I will try to give an historical overview on why and how this correspondence was established, travelling back in time to see how the notion of "proof" evolved since the greeks (our historical lower bound in this talk) until becoming a major concept not only for mathematics but also for the development of programming languages (among other things). In between, I may talk about intuitionistic logic, proof assistants, realizability (my favorite topic), model theory, etc. This list is non-exhaustive, and in particular I would be glad to extend it with any related subsequent topic that may interest you (if so, you should send me an email: "Salut, je me suis toujours demandé ce que c'était qu'une théorie des types, tu pourrais en parler ?", and I may try to include a slide or two, with a probability highly related to the date of your mail).
Conference : Journée d'Ouverture Scientifique (JOS), 1ère édition - Informatique
15/11/2022 à 08h30
Les LIS est partenaire de la 1ère Journée d'Ouverture Scientifique consacrée à l'Informatique mardi 15 novembre 2022 sur le site Saint Charles. Destinée aux étudiants en informatique de diverses formations, elle a pour objectifs d’élargir les horizons scientifiques et professionnels, d’alimenter la réflexion sur leur devenir et de favoriser les échanges entre licences/masters/entreprises/chercheurs. Au programme: de la blockchain à la question des femmes en informatique en passant par les différents métiers, profitez des conférences, rencontres et tables rondes destinés aux étudiants, en présence d'entreprises, de jeunes chercheurs doctorants et de chercheurs plus expérimentés.Programme et inscriptions: https://jos-2022.lis-lab.fr/ .
Cette journée est soutenue par le LIS, l'Institut Archimède/Tiger, l'ED maths-info, le réseau Les Entreprises Pour la Cité, la Licence MPCI et plusieurs formations en informatique (licence et master).
Conference : BDA'2022 - 38èmes journées de la conférence BDA « Gestion de Données – Principes, Technologies et Applications »
24/10/2022 à 00h00
La conférence BDA est un événement annuel incontournable de la communauté gestion de données en France, qui met en exergue les nombreux thèmes de recherche liés à la gestion de données tels que les Entrepôts de données, le Big-Data, la gestion de flux, la qualité, la sécurité, la fouille de données, ou encore le Web sémantique. Site web de la conférence : https://bda2022.sciencesconf.org/Seminaire : Séminaire de Théorie du Contrôle
20/10/2022 à 14h30
Eugenio Pozzoli (IMB) Contrôlabilité des systèmes quantiques en dimension infinie https://pole-acs.lis-lab.fr/Seminaire : Séminaire CANA - Ravi Kunjwal
18/10/2022 à 14h00
Orateur : Ravi Kunjwal (Centre for Quantum Information and Communication, Université libre de Bruxelles)Lieu : TPR2/04.05 (Luminy)
Titre : Contextuality in composite systems: entanglement vs. the Kochen-Specker theorem
Abstract : The Kochen-Specker (KS) theorem is often taken as a notion of nonclassicality that is independent of entanglement since it is provable on a three-dimensional Hilbert space. However, the smallest system on which both the KS theorem and entanglement are meaningful notions of nonclassicality is a two-qubit system. I will present some recent work on the necessity of entanglement in proofs of the KS theorem on multiqubit systems. We show two key results: firstly, that any proof of the KS theorem that uses KS sets necessarily requires entangled measurements, and secondly, that a statistical proof of the KS theorem with unentangled measurements on a multiqubit state exists if and only if this state can witness a Bell inequality violation. We also obtain an overall understanding of the relationship between unentangled Gleason and KS theorems on multiqudit systems in general. Time permitting, I will also discuss some implications of these results for the role of contextuality as a resource for multiqubit quantum computation with state injection. Based on arXiv:2109.13594.
Conference : Séminaire CANA - Aymeric Picard Marchetto
04/10/2022 à 14h00
Orateur : Aymeric Picard Marchetto (PhD I3S)Lieu : TPR2/04.05 (Luminy) et en visio
Titre : Given an automata network, many results show that some dynamical properties can be deduced from its interaction digraph. These dynamical properties are often invariant by isomorphism: number of fixed points, of images, length of limit cycles and transients... But the interaction digraph is not invariant by isomorphism: tow isomorphic automata networks (with the same alphabet and the same number of automata) can have very different interaction digraphs.
In this talk, we study this phenomena. For that, given an automata network f with n automata, we denote by G[f] the set of interaction digraphs of automata networks isomorphic to f. Hence G[f] is a set of digraphs with n vertices.
In particular, we show that if n>4, and f is neither the identity or constant, then G[f] contains the complete digraph. We also prove that G[f] always contains a digraph with minimum in-degree at most some constant that only depend on the alphabet size. Consequently, G[f] cannot only contain the complete digraph, but we show that there is f such that G[f] only contain digraphs with at least n^2/4 arcs. Finally, we prove that there is f such that G[f] contains all the digraphs with n vertices, excepted the empty one.
Seminaire : Séminaire DYNI - Dan Stowell - Deep embedding methods for high-resolution animal sound recognition
29/09/2022 à 14h30
Automatic detection and classification of sound events is a promising tool for monitoring wildlife. However - since there are hundreds of species and sounds, and complex noisy soundscapes, machine learning needs to be raised to a very high level of fine-grained precision and robustness. I will report on deep embeddings trained with loss functions designed to reflect fine-grained aspects of animal sound discrimination: hierarchical individual recognition, few-shot learning and perceptual discrimination. Biography: Dan Stowell is Associate Professor of AI & Biodiversity, jointly appointed at Tilburg University and Naturalis Biodiversity Center (NL). Since 2012 he has led research on computational bioacoustics using machine learning and signal processing. He is a co-founder of the data challenge "detection and classification of sound scenes and events (DCASE)", now an annual IEEE workshop and challenge. He is cofounder and CTO of Warblr Ltd (UK), a phone app that automatically recognises bird sounds - the app has received awards and copious press coverage, and has tens of thousands of regular users around the UK. In the Netherlands he is involved in many funded projects to bring AI-powered biodiversity monitoring to fruition. Lieu: X133, UTLN, campus de La GardeSeminaire : Séminaire ACRO
12/09/2022 à 10h00
Séminaire de Jean-Christophe Godin, en salle 4.05 du TPR2 à Luminy. Titre : On List Coloring with Separation of the Complete Graph and Set-System intersections Résumé : We consider the following list coloring with separation problem: Given a graph G and integers a, b, find the largest integer c such that for any list assignment L of G with |L(v)| = a for any vertex v and |L(u) ∩ L(v)| ≤ c for any edge uv of G, there exists an assignment φ of sets of integers to the vertices of G such that φ(u) ⊂ L(u) and |φ(v)| = b for any vertex u and φ(u) ∩ φ(v) = ∅ for any edge uv. Such a value of c is called the separation number of (G, a, b). Using a special partition of a set of lists for which we obtain an improved version of Poincaré’s crible, we determine the separation number of the complete graph Kn for some values of a, b and n, and prove bounds for the remaining values. Travail en commun avec Rémi Grisot et Olivier TogniSeminaire : Séminaire CANA : Kévin Perrot
19/07/2022 à 14h00
Orateur : Kévin Perrot (LIS)Lieu : TPR2/04.05 (Luminy)
Titre : Trois exemples magiques d’algorithmes randomisés
Abstract : 1) Compter jusqu'à 10^309 sur ses 10 doigts. 2) Obtenir un multiplicateur robuste à partir d'un multiplicateur foireux.
3) Preuves à divulgation nulle de connaissance (zéro-knowledge proofs).
Ces exemples sont tirés de l'article “Randomness + determinism = progresses: Why random processes could be favored by evolution” par Nicolas Schabanel en 2012.
Seminaire : Matinée des Jeunes Scientifiques du LIS
12/07/2022 à 09h30
Une matinée de science dédiée à nos étudiant·e·s de L1 qui participent à la vie du LIS dans le cadre d’un stage « Incubateur de jeunes scientifiques » promu par la Faculté des Sciences AMU.
Cette matinée aura lieu le 12 juillet 2022 à partir de 9h30 dans la salle 04.05 du bâtiment TPR2 sur le site du Luminy et il sera également possible d’y participer par Zoom.
Voici le programme de la matinée :
- 9h30 Tamazouzt Ait-Eldjoudi et Antonio Mattar : Des alligators au lambda-calcul (encadré·e·s par Benjamin Monmege)
- 10h10 Redouane Benkhemou : Deep Learning VS. Modélisation et Simulation DEVS : application aux portes logiques (encadré par Amine Hamri)
- 10h40 Mathieu Cambon, Marc-Antoine Poquet et Rayan Saadessaoud : Questions autour de la philosophie de l'informatique, de l'intelligence artificielle et des sciences cognitives (encadrés par Thomas Schatz)
- 11h30 Ekaterina Timofeeva : Développement de logiciel pour l’étude de la décomposition de systèmes dynamiques (encadrée par Antonio E. Porreca)
- 12h00 Alexander Zinoni : Vulnérabilité d'une implémentation de ECDSA dans Java (encadré par Jean-Marc Talbot)
Seminaire : Séminaire CANA : Nathanaël Eon
28/06/2022 à 14h00
Orateur : Nathanaël Eon (PhD CANA, LIS)Lieu : TPR2/04.05 (Luminy)
Titre : From global (color-blind) symmetry to local (gauge) invariance in cellular automata
Abstract : In this talk, I will first introduce the concept of global (a.k.a. color-blind) and local (a.k.a. gauge) symmetries in cellular automata. The essence of those symmetries is for the cellular automata to be invariant under a change of the configuration, either done globally (applying the same transformation at every position) or locally (applying a different transformation at every position). Hence, a local symmetry is a priori stronger than a global one. In order to enforce the local symmetry, an extension of CA is introduced and an interesting equivalency result follows: globally symmetric CA are exactly those which can be extended into locally invariant ones (through a specific extension). Such result makes formal a folklore perspective in Physics which says that any local symmetry necessarily arise from an already existing global one. I will then provide two constructive proofs of universality for locally invariant cellular automata.
The results provided in this talk can be found on arXiv:2102.06912.
Seminaire : Séminaire CANA : Éric Rémila
21/06/2022 à 14h00
Orateur : Éric Rémila (GATE LSE)Lieu : TPR2-04.05
Titre : Influence: a partizan scoring game on graphs
Abstract : We introduce the game influence, a scoring combinatorial game, played on a directed graph where each vertex is either colored black or white. The two players, Black and White, play alternately by taking a vertex of their color and all its successors (for Black) or all its predecessors (for White). The score of each player is the number of vertices he has taken. We prove that influence is a nonzugzwang game, meaning that no player has interest to pass at any step of the game, and thus belongs to Milnor’s universe. We study this game in the particular class of paths where black and white vertices are alternated. We give an almost tight strategy for both players when there is one path. More precisely, we prove that the first player always gets a strictly better score than the second one, but that the difference between the scores is bounded by 5. Finally, we exhibit some graphs for which the initial proportion of vertices of the color of a player is as small as possible but where this player can get almost all the vertices.
Seminaire : Demi-journée pôle calcul - Intelligence Artificielle
16/06/2022 à 09h30
Orateurs :- Joao Marques-Silva "Logic-Based Explainability in Machine Learning”
- Stéphane Grandcolas (LIS) "WRM: a metaheuristic algorithm for ship weather routing"
- Matthieu Py (LIS) "Production de certificats pour le problème Max-SAT"
Pour les abstracts, rendez-vous sur le site des demi-journées du pôle : https://demi-journees-pole-calcul.lis-lab.fr
Seminaire : Séminaire CANA : Kevissen Sellapillay
31/05/2022 à 14h00
Orateur : Kevissen Sellapillay (LIS & CPT)Salle : TPR2-04.05
Titre : Interaction graphs of isomorphic automata networks
Abstract : Entanglement is a quantum property with no classical counterpart. We briefly review entanglement, its definition and quantities to measure it. We then present a perturbation of a quantum cellular automaton based on rule 201 and study its entanglement propagation properties. This quantum cellular automaton breaks the Hilbert space into different ergodic sectors.
Seminaire : Séminaire du Pôle SD : Interprétabilité /Explicabilité des modèles d'apprentissage
09/05/2022 à 10h30
Le prochain séminaire du pôle se déroulera donc lundi prochain le 9 mai de 10h30 à 12h00 à St Charles (Frumam) et dont le thème est "Interprétabilité /Explicabilité des modèles d'apprentissage". Nous aurons le plaisir d'écouter trois présentations : Hanwei Zhang : Présentation générale des méthodes d'interprétabilité Felipe Torres : Méthodes dédiées à l'interprétabilité des images Hamed Benazha : Méthodes dédiées l'interprétabilité des séquencesSeminaire : Demi-journée pôle calcul - Complexité et Modèles de calculs
05/05/2022 à 10h00
Orateurs :- Édouard Bonnet "Graph decompositions and their algorithms”
- Karoliina Lehtinen (LIS) "Un peu de non-déterminisme peut aller loin: un aperçu des automates déterministes en histoire"
Pour les abstracts, rendez-vous sur le site des demi-journées du pôle : https://demi-journees-pole-calcul.lis-lab.fr
Conference : Conférence par Hervé Glotin, suivie par l'écoute de deux oeuvres sonores composés par Maxence et Léonore Mercier
14/04/2022 à 16h00
Impossible de parler Acoustique à Marseille sans évoquer l'acoustique en milieu marin, qu'elle concerne la propagation des sons à travers les mers et les océans, les chants produits par une faune marine d'une extrême diversité ou encore - préoccupation beaucoup plus récente - de l'impact de l'activité maritime humaine sur cet écosystème si fragile. https://cfa2022.sciencesconf.org/resource/page/id/25 Cinéma Les Variétés 37 Rue Vincent Scotto 13001 MarseilleSeminaire : Séminaire MoVe avec K.S. Thejaswini
07/04/2022 à 10h30
Où ? 4.05 TPR2 Luminy Quoi ? A Symmetric Attractor-Decomposition Lifting Framework for Solving Parity games. Mais encore? In this talk, we will introduce the framework of Symmetric Attractor-Decomposition Lifting. We show how this helps us understand as well as obtain a quadratic improvement to the runtime of several pre-existing algorithm. This is joint work with Marcin Jurdzinski, Remi Morvan and Pierre Ohlmann.Seminaire : Séminaire CANA : Sara Riva
05/04/2022 à 14h00
Orateur : Sara Riva (Université Côte D'Azur et I3S Sophia Antipolis)Salle : TPR2-04.05
Titre : A Pipeline for Solving Equations over Discrete Dynamical Systems
Abstract : Finite Discrete Dynamical Systems (DDS) are a formal model to study complex phenomena appearing in many different domains. Hypotheses on the fine structure of the system can be modeled via polynomial equations over DDS. For example, AX=B represents the hypothesis that the dynamics of B is given by the joint action of a known system A and an unknown one X. Finding X would validate the hypothesis; the hypothesis is invalid if no solution exists. In general, solving generic equations over DDS has been proved undecidable. In the hypothesis validation case, a possible approach is to study the solutions through a finite number of different abstractions of the problem. Each abstraction allows studying specific properties and parts of specific dynamics. We focus on hypotheses about the cardinality of the set of states, the cyclic behaviour and the transient behaviour of DDS. We introduce a complete pipeline based on Multi-valued decision diagrams to validate hypotheses on the cardinality of the set of states and on the asymptotic behaviour, contained in the cyclic parts, of a DDS. These results are a step forward in the analysis of complex dynamics graphs as those appearing, for instance, in biological regulatory networks or in systems biology. Furthermore, this approach opens up new research challenges in the field of ordered decision diagrams and their operations.
Seminaire : Séminaire DANA - Amélioration de l'apprentissage explicable/interprétable fondé sur FCA
29/03/2022 à 16h10
Orateur : Nida MeddouriLien Zoom : https://univ-amu-fr.zoom.us/j/83522684614?pwd=d1FBZmhBZnZ0M1BpUnRlRWJ5ZU5CQT09
Titre : Amélioration de l'apprentissage explicable/interprétable fondé sur FCA
Résumé : Formal Concept Analysis (FCA) est une formalisation de la notion philosophique de concept définie comme étant un couple d’extension et de compréhension du concept. Un des principaux atouts de FCA réside dans ses propriétés de visualisation. En effet, FCA produit des treillis de concepts formels qui peuvent être représentés par un graphe ; et facilitent ainsi la tâche du classifieur dans la découverte de connaissances. La classification par ACF est une approche de fouille de données explicable/interprétable qui permet d’extraire des corrélations, des motifs et des règles, selon les concepts générés à partir des données symboliques. Mes recherches m’ont permis d’améliorer les performances d’un classifieur fondé sur FCA en proposant des méthodes d’apprentissage séquentiel. Ces méthodes sont à la fois itératives et adaptatives. Elles ont pour but de combiner des classifieurs de concepts formels afin d’améliorer la précision et l’efficacité. Leurs performances théoriques sont garanties et approuvées. Une autre contribution permet de booster adaptativement des classifieurs (quel que soit l’algorithme d’apprentissage) en tenant compte de leurs diversités. Cette méta-méthode a la particularité d’éviter le sur-apprentissage. Une autre méthode proposée permet de générer parallèlement un ensemble de classifieurs de concepts formels à partir d’un certain nombre de groupements disjoints et stratifiés de données. Vu son aspect parallèle et sa capacité à s’adapter pour traiter des grandes quantités de données, je me suis intéressé à la mise en cloud de cette méthode. Une nouvelle mesure de pertinence d’attribut a été proposée. Elle s’adapte au mieux avec un classifieur fondé sur FCA.
Seminaire : Séminaire DANA - ATLAS data, physicists' treat to treat
29/03/2022 à 14h00
Orateur : Thomas CalvetLien Zoom : https://univ-amu-fr.zoom.us/j/84940669492?pwd=MklWK1pQbHozUjRZUDU1MVhmc2dVdz09
Titre : ATLAS data, physicists' treat to treat
Résumé : Le LHC au CERN est le plus grand générateur mondial de données pour caractériser la matière dans son état connu le plus fondamental. Les collisions proton-proton produites par le LHC sont observées par quatre détecteurs géants. ATLAS est un de ces détecteurs. De la taille d'un petit immeuble (40m de long sur 20m de haut), ce détecteur offre une excellente résolution spatiale (de l'ordre de la centaine de micromètre) et temporelle (collisions toutes les 25ns) sur les produits des collisions. Pour ce faire, il génère des quantités massives de données dont l'exploitation est le cœur d'œuvre des physiciens du CERN. Deux temps se distinguent. Sur les premières microsecondes, des algorithmes automatisés doivent être capable de reconstruire les propriétés physique de bases à partir des données brutes pour décider de la sauvegarde ou du rejet des données de chaque événement. Les données sauvegardées sont ensuite étudiées avec minutie pour des mesures de hautes précisions qui sont confrontés aux modèles théoriques. Cette présentation sert un objectif double : mettre en perspective les défis de gestion des données d'ATLAS à ses différents niveaux et les illustrer par mes travaux notamment dans le domaine des IA.
Seminaire : Séminaire DANA - Extraction de motifs dans des données spatio-temporelles : application au suivi environnemental
29/03/2022 à 09h30
Orateur : Frédéric Flouvat (MCF, HDR, Université de la Nouvelle-Calédonie)Lien Zoom : https://univ-amu-fr.zoom.us/j/86329875449?pwd=VU95K2R4bVdFMWc4NEpwK295MEhkZz09
Titre : Extraction de motifs dans des données spatio-temporelles : application au suivi environnemental
Résumé : Ces dix dernières années, la quantité de données collectées a explosé. Au-delà des volumes de données engendrés, leur complexité a aussi considérablement augmenté. Même si les avancées ont été nombreuses, les verrous restent encore nombreux avant de réellement pouvoir valoriser toutes ces informations. L'augmentation de la puissance de calcul des ordinateurs, bien que continue, n'est pas suffisante face à des tâches d'analyse de plus en plus complexes. Dans ce contexte, une problématique a été notamment étudiée par la communauté scientifique: l'extraction de motifs intéressants ("pattern mining"). Ces motifs représentent des régularités suivies par une partie des données (on parle aussi de "modèles locaux"). Cette problématique a été introduite dans les années 90 avec pour application l'analyse des paniers d'achats des consommateurs. Une grande variété de types de motifs et d'applications a été étudiée depuis (p.ex. dans les domaines de la sécurité, de la médecine, ou du commerce). Toutefois, les défis restent importants, notamment lorsqu'il s'agit d'analyser des données environnementales. En effet, les phénomènes sous-jacents et les données collectées sont complexes et variées (p.ex. images satellitaires, données collectées sur le terrain, données issues de modèles). L'exploitation de telles données est difficile et nécessite des méthodes d'analyse avancées. Ce séminaire présentera plusieurs travaux visant à extraire des motifs spatio-temporels plus riches et plus pertinents dans ces masses de données complexes.
Seminaire : Séminaire G-MOD - Simulation de rubans et validation physique
28/03/2022 à 16h30
Lien zoom : https://univ-amu-fr.zoom.us/j/83169477124?pwd=Q05rS2lnNzhqNllJODhKK3c2VzMvdz09 Si à l'origine l'informatique graphique concernait surtout l'animation, de nos jours les modèles de la communauté graphique ont tendance à être appliqués au monde réel par exemple dans le domaine de la fabrication. Cependant, ces modèles proposent parfois des énergies ad hoc et la prédiction numérique peut s'éloigner significativement du résultat physique. Faut-il alors utiliser des modèles plus mécaniques ? Dans un premier temps, je présenterai mon travail de thèse sur la modélisation de rubans. On verra par exemple que les tiges ne se comportent pas comme des rubans. Une bonne partie de mon travail consiste à valider le modèle que j'ai établi et à en montrer les limites. Dans un second temps, je parlerai de validation de modèles par protocoles expérimentaux relativement simple à mettre en place. Ce travail collaboratif s'inspire de protocoles mécaniques pour valider des modèles de tiges, rubans, coques. Il serait dommage de rejeter un modèle numérique, sous prétexte qu'il n'a pas assez de fondements mécaniques. On peut l'étudier pour comprendre sous quelles hypothèses son comportement est prédictif. On conclura ainsi que le choix du modèle utilisé doit correspondre à son usage. Il serait judicieux si cela n'a pas déjà été fait de tester le comportement physique de ce modèle.Seminaire : Séminaire G-MOD - Simulation de rubans et validation physique
28/03/2022 à 16h30
Si à l'origine l'informatique graphique concernait surtout l'animation, de nos jours les modèles de la communauté graphique ont tendance à être appliqués au monde réel par exemple dans le domaine de la fabrication. Cependant, ces modèles proposent parfois des énergies ad hoc et la prédiction numérique peut s'éloigner significativement du résultat physique. Faut-il alors utiliser des modèles plus mécaniques ? Dans un premier temps, je présenterai mon travail de thèse sur la modélisation de rubans. On verra par exemple que les tiges ne se comportent pas comme des rubans. Une bonne partie de mon travail consiste à valider le modèle que j'ai établi et à en montrer les limites. Dans un second temps, je parlerai de validation de modèles par protocoles expérimentaux relativement simple à mettre en place. Ce travail collaboratif s'inspire de protocoles mécaniques pour valider des modèles de tiges, rubans, coques. Il serait dommage de rejeter un modèle numérique, sous prétexte qu'il n'a pas assez de fondements mécaniques. On peut l'étudier pour comprendre sous quelles hypothèses son comportement est prédictif. On conclura ainsi que le choix du modèle utilisé doit correspondre à son usage. Il serait judicieux si cela n'a pas déjà été fait de tester le comportement physique de ce modèle.Seminaire : Séminaire GMOD - Towards a standardized system that transforms textured 3D geometry into knitted textiles
11/03/2022 à 14h00
Invité (visio) : Georges Nader Salle : 5.37 Zoom : https://univ-amu-fr.zoom.us/j/4554512911?pwd=WmJJVHBPNExMTXdhZ2xLNjJkY0NzUT09 Titre : Towards a standardized system that transforms textured 3D geometry into knitted textiles. Résumé : We introduce a flexible and customizable system for the computational design and production of functional, multi-material, and three-dimensional knitted textiles. Our system simplifies the knitting of 3D objects with complex, varying patterns that use multiple yarns and stitch patterns by separating the high-level design specification in terms of geometry, stitch patterns, materials or colors from the low-level, machine-specific knitting instruction generation. Starting from a triangular 3D mesh and a 2D texture that specifies knitting patterns on top of the geometry, our system generates the required machine instructions in three major steps. First, the input is processed and the KnitNet data structure is generated. This graph structure serves as an abstract interface between the high-level geometric and knitting configuration and the low-level, machine-specific knitting instructions. Second, a graph rewriting procedure is applied on the KnitNet that produces a sequence of abstract machine actions. Finally, the low-level machine instructions are generated by adapting those abstract actions to a specific machine context. We showcase the potential of this computational approach by designing and fabricating a variety of objects with complex geometries, multiple yarns and multiple stitch patterns. Venez nombreux !Seminaire : Séminaire CANA : Kévin Perrot
08/03/2022 à 14h00
Orateur : Kévin Perrot (CANA, LIS)Salle : TPR2-04.05
Titre : Théorème du point fixe de Kleene en calculabilité
Abstract : Pour toute transformation de programme h calculable, il existe un programme n tel que n et h(n) font la même chose. Ce théorème est génial, et sa preuve d'une simplicité déconcertante. De plus ses corollaires sont nombreux, comme l'indécidabilité de l'arrêt, et l'existence de quine (programme qui affiche en sortie son propre code) dans tout langage de programmation acceptable. On programmera un quine ensemble :-) Cet exposé est tiré d'une séance de l'UE Calculabilité Avancée en M1 Info, pas de résultat nouveau, juste un peu de culture.
Seminaire : Séminaire GMOD - Progressivité et Analyse Topologique de Données Scalaires
04/03/2022 à 10h00
Invité : Jules Vidal (LIP6) Salle : 5.37 Zoom : https://univ-amu-fr.zoom.us/j/4554512911?pwd=WmJJVHBPNExMTXdhZ2xLNjJkY0NzUT09 Titre : Progressivité et Analyse Topologique de Données Scalaires Résumé : L’analyse topologique de données forme une famille d’outils qui permettent l’extraction générique et efficace de caractéristiques structurelles dans les données. Cependant, bien que ces techniques aient des complexités asymptotiques connues et raisonnables, elles sont rarement interactives en pratique sur des jeux de données réels, ce qui limite leur utilisation pour l’analyse et la visualisation interactives de données. Dans cette présentation je décrirai les travaux réalisés pendant ma thèse, durant laquelle j'ai cherché à développer des approches progressives pour l’analyse topologique de données scalaires. Dans ce contexte, une méthode progressive est une technique qui peut être interrompue pour fournir rapidement un résultat approché exploitable, et est capable de le raffiner graduellement. Dans un premier temps, nous présentons une représentation hiérarchique des données d’entrée, qui permet de définir des algorithmes topologiques coarse-to-fine efficaces. En conséquence, nous introduisons deux algorithmes progressifs pour le calcul des points critiques et du diagramme de persistance d’un champ scalaire. Ces méthodes fournissent des sorties interprétables en cas d’interruption, offrent un retour visuel continu tout au long du calcul et sont plus rapides en pratique que leurs homologues non progressifs. Ensuite, nous revisitons ce cadre progressif pour introduire un algorithme pour le calcul approché du diagramme de persistance d’un champ scalaire, avec des garanties sur l’erreur d’approximation associée. Enfin, afin d’effectuer une analyse visuelle de données d’ensemble, nous présentons un nouvel algorithme progressif pour le calcul du barycentre de Wasserstein d’un ensemble de diagrammes de persistance, une tâche notoirement coûteuse. Nous étendons cette méthode à un algorithme de classification topologique de données d’ensemble, qui est progressif et capable de respecter une contrainte de temps. Venez nombreux !Seminaire : Séminaire GMOD - Rendu basé physique de matériaux scintillants
21/02/2022 à 10h00
Invité : Xavier Chermain Salle : 5.37 Zoom : https://univ-amu-fr.zoom.us/j/4554512911?pwd=WmJJVHBPNExMTXdhZ2xLNjJkY0NzUT09 Titre : Rendu basé physique de matériaux scintillants Résumé : Le rendu basé physique est un processus important en informatique graphique, qui prend en entrée une scène 3D composée d'une caméra, de lumières et de formes géométriques ayant toutes un matériau. La propagation de la lumière est simulée en se basant sur des équations physiques, permettant d'obtenir une photo réaliste de la scène 3D virtuelle. La modélisation d'apparence est indispensable pour représenter la grande diversité d'apparences du monde réel. Dans cet exposé, je parlerai de la modélisation d'apparence des matériaux scintillants. Ce type d'apparence est difficile à modéliser à cause des fortes variations de réflexions lumineuses lors d'un petit changement de position ou de direction d'observation. Je parlerai de mes principales contributions dans ce domaine. Venez nombreux !Conference : Séminaire CaNa -- Ilya Galanov
08/02/2022 à 14h00
Orateur: Ilya GalanovSalle: TPR2-04.05
Titre : Purely local self-assembly algorithm for a quasiperiodic octagonal tiling
Abstract: Self-assembly is the process in which the components of a system, whether molecules, polymers, or macroscopic particles, are organized into ordered structures as a result of local interactions between the components themselves, without exterior guidance. This talk is devoted to the self-assembly of aperiodic tilings. Aperiodic tilings serve as a mathematical model for quasicrystals - crystals that do not have any translational symmetry. Because of the specific atomic arrangement of these crystals, the question of how they grow remains open. Simulations strongly support the evidence that the algorithm we developed grows aperiodic tilings up to an unavoidable but neglectable proportion of missing tiles. In this talk, we state the first theorem regarding the Golden-Octagonal tilings and formulate conjectures for future results.
Rencontre : Demi-journée pôle calcul - Algorithmique et Structures Discrètes
20/01/2022 à 09h30
Orateurs :- Janna Burman (LRI) "Time-Optimal Self-Stabilizing Leader Election in Population Protocols”
- Alessia Milani (LIS)
- Eloi Perdereau (LIS)
Pour les abstracts, rendez-vous sur le site des demi-journées du pôle : https://demi-journees-pole-calcul.lis-lab.fr
Seminaire : Séminaire G-MOD - L’apprentissage profond des nuages de points 3D : Application aux données LiDAR
14/01/2022 à 14h00
Dans le cadre des séminaires G-MOD, nous avons le plaisir d'accueillir Jules Morel. Résumé : La capacité de la technologie LiDAR à capturer des informations détaillées sur la structure des forêts a attiré une attention croissante de la part de la communauté des écologues et des forestiers. Le LiDAR terrestre, notamment, apparaît comme un outil prometteur pour recueillir les caractéristiques géométriques des arbres à une précision millimétrique. Puisque cette technologie produit des quantités de données élevées, la recherche actuelle se concentre sur la mise au point de chaîne de traitement automatique. Cette présentation exposera comment l'utilisation du deep learning répond à une des étapes clés de cette chaîne de traitement: la classification des points 3D.Seminaire : Séminaire MoVe avec Marie Fortin
09/12/2021 à 10h30
Title : How undecidable are HyperLTL and HyperCTL*? Abstract: Temporal logics for the specification of information-flow properties are able to express relations between multiple executions of a system. Two of the most important such logics are HyperLTL and HyperCTL*, which generalise LTL and CTL* by trace quantification. It is known that this expressiveness comes at a price, i.e., satisfiability is undecidable for both logics. We settle the exact complexity of these problems, showing that both are in fact highly undecidable: we prove that HyperLTL satisfiability is \Sigma^1_1-complete and HyperCTL* satisfiability is \Sigma^2_1-complete. To prove \Sigma^2_1 membership for HyperCTL*, we prove that every satisfiable HyperCTL* formula has a model that is equinumerous to the continuum, the first upper bound of this kind. We prove this bound to be tight. This is joint work with Louwe B. Kuijer, Patrick Totzke and Martin Zimmermann. Salle 4.05 TPR2 (Luminy)Seminaire : Séminaire CaNa -- Théo Grente
07/12/2021 à 14h00
Orateur: Théo GrenteSalle: TPR2-04.05
Titre : Conjunctive grammars, cellular automata and logic
Abstract: Conjunctive grammars are an extension of context free grammars with a conjunction operation. Their expressive power (even on a unary alphabet) is largely unknown.
When restricting time, space or even communication, cellular automata (CA) can act as languages recognizer defining complexity classes.
The goal of this talk is to prove the inclusion of conjunctive languages in one of CA complexity classes.
The proof uses a programming method which relies on exact characterizations of interesting CA complexity classes by sub-logics of ESO (existential second-order logic) with Horn formulas as their first-order part. By using this method, we just have to define conjunctive grammars in our logic to obtain an inclusion result.
Seminaire : Séminaire MoVe avec Antonio Casares
02/12/2021 à 10h30
Lieu: Salle 4.05 du bâtiment TPR2 (Luminy)Title: On a correspondence between memory structures for Muller games and Rabin automata
Abstract: In the study of infinite duration games over graphs, an important parameter is the amount of memory required by the players to play optimally. Two different kinds of memory structures can be distinguished: those that may depend in the particular structure of each specific game (unconstrained memories), and those that can only depend on the sequence of colors that has been produced (chromatic memories). In this talk, I will discuss these two kinds of memories in the case of Muller games. We show that chromatic memories exactly correspond to deterministic Rabin automata, while unconstrained memories correspond to Good-For-Games automata. Moreover, we prove that the difference on the size between the two them can be exponential in the number of colors defining the winning condition. This is a joint work with Thomas Colcombet and Karoliina Lehtinen.
Seminaire : Séminaire du pôle SD - Demi-Journée des nouveaux entrants
29/11/2021 à 09h00
Nous organisons la journée des nouveaux entrants le 29 novembre de 9h à 13h. Les docs, post-doc, et permanents ayant intégrés le pôle dans les deux dernières années viendront présenter leur travaux. Et un traditionnel buffet suivra.Seminaire : Journée Thématique Quantique
26/11/2021 à 10h00
La journée du 26 novembre au CIRM a l'objectif principal de faire rencontrer dans une seule salle, pour la première fois, tous les chercheurs AMU sur le domaine "Quantique" interessés à s'inscrire dans la récente stratégie nationale sur les technologies quantiques, notamment d’un point de vue informatique/mathématique/physique théorique.Seminaire : Séminaire MoVe - Filip Mazowiecki
25/11/2021 à 13h00
Lieu: Luminy, batiment TPR2, salle 5.37Titre: The boundedness and zero isolation problems for weighted automata over nonnegative rationals
Abstract: We consider weighted automata over the semiring of nonnegative rationals, which generalise probabilistic automata. The two problems boundedness and zero isolation ask whether there is a sequence of words that converge to infinity and zero, respectively. In the general model both problems are undecidable so we focus on the copyless linear restriction. There, we show that the boundedness problem is decidable, exploiting the Simon’s factorization forest theorem. As for the zero isolation problem we need to further restrict the class. We obtain a model, where zero isolation becomes equivalent to coverability of orthant vector addition systems (OVAS), a new model in the VAS family interesting on its own. Assuming Schanuel’s conjecture is true, we prove decidability of coverability for three-dimensional OVAS, which gives decidability of zero isolation in a model with at most three registers.
Seminaire : IA-SANTE : colloque Sciences Numériques et IA pour la santé à AMU
25/11/2021 à 09h00
Aix-Marseille Université organise les 25 et 26 Novembre 2021 un colloque en « Sciences Numériques et Intelligence Artificielle pour la Santé ». L’objectif principal sera de réunir pour la première fois l’ensemble des acteurs d’Aix-Marseille Université et du Centre Hospitalier Universitaire impliqués dans la création de l’institut Laënnec, institut d'établissement AMU en "sciences numériques et intelligence artificielle pour la santé" en partenariat avec l’APHM et l’IPC.Seminaire : Séminaire CaNa -- Silvère Gangloff
23/11/2021 à 14h00
Orateur: Silvère GangloffTitre : Classes de transitivité pour les sous-décalage de type fini multi-dimensionnels.
Abstract: Ce travail est en commun avec B.Hellouin et P.Oprocha. Les sous-décalages de type fini multidimensionnels ont été étudiés dans les dernières décennies à travers le spectre de propriétés topologiques telles que la transitivité ou le mélange. Dans des travaux récents, nous avons montré, avec B.Hellouin et M.Sablik, qu'en quantifiant ces propriétés, il est possible de caractériser la complexité de ces systèmes dynamique en fonction de la quantité de transitivité/mélange (en particulier du point de vue calculabilité). Cependant les différentes classes de transitivité (relatives à cette quantification) sont mal comprises dans le cas général. Avec B.Hellouin et P.Oprocha, nous travaillons à caractériser ces classes dans le cadre restreint des Hom shifts, c'est à dire les sous-décalages définis par des ensembles de motifs interdits consistant en des dominos dont les symboles ne sont pas voisins dans un graphe fini non-orienté. Dans cet exposé, je présenterai le problème, ainsi que des résultats obtenus et attendus dans cette direction, qui laissent espérer une caractérisation complète des classes de transitivité dans le cas des Hom shifts.
Rencontre : Demi-journée pôle calcul - Géométrie et Topologie du Calcul
18/11/2021 à 00h00
Orateurs :- Dmitry Sokolov (LORIA) "How to compute locally invertible maps"
- Corentin Travers (LABRI) "Synchronous t-Resilient Consensus in Arbitrary Graphs"
- Victor Chepoi (LIS) "1-safe Petri nets and special cube complexes"
Pour les abstracts, rendez-vous sur le site des demi-journées du pôle : https://demi-journees-pole-calcul.lis-lab.fr
Conference : Séminaire CaNa -- Leonardo Novo
16/11/2021 à 14h00
Speaker: Leonardo NovoTitle: Spatial search by continuous-time quantum walk
Abstract: I will present two recent contributions about the performance of quantum search algorithms based on continuous-time quantum walks [1,2]. First, I will present some general results about the performance of the algorithm introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], which uses a continuous-time quantum walk to find a marked node on a graph of n nodes. This algorithm is said to be optimal if it can find any of the nodes in the graph in O(sqrt(n)) time. I will present conditions, based on the spectrum of the Hamiltonian driving the quantum walk, that can be used to predict whether the algorithm is optimal on a given graph. In the second part of the talk, I will present a new algorithm based on Hamiltonian evolution that finds marked nodes on any ergodic reversible Markov chain P quadratically faster than its classical hitting time. This algorithm can be seen as a quantum walk on the edges of a Markov chain and its performance matches that of discrete-time quantum walk search algorithms based on the Szegedy formalism. This work improves upon the recent work of [Phys. Rev. A 102, 022227 (2020) ] and finally closes a theoretical gap between the performance of continuous-time and discrete-time quantum walk approaches for search.
References:
- On the optimality of spatial search by continuous-time quantum walk, Shantanav Chakraborty, Leonardo Novo, and Jérémie Roland, Phys. Rev. A 102, 032214 (2020)
- Finding a marked node on any graph by continuous-time quantum walk , Shantanav Chakraborty, Leonardo Novo, and Jérémie Roland, Phys. Rev. A 102, 022227 (2020)
Seminaire : Séminaire CaNa -- Shyan Shaer Akmal
04/11/2021 à 15h00
Orateur: Shyan Shaer AkmalTitle: Majority-3SAT (and Related Problems) in Polynomial Time
lien zoom
Abstract: Majority-SAT is the problem of determining whether an input n-variable formula in conjunctive normal form (CNF) has at least 2^{n-1} satisfying assignments. Majority-SAT and related problems have been studied extensively in various AI communities interested in the complexity of probabilistic planning and inference. Although Majority-SAT has been known to be PP-complete for over 40 years, the complexity of a natural variant has remained open: Majority-kSAT, where the input CNF formula is restricted to have clause width at most k.
It recent work, joint with Ryan Williams, we prove that for every k, Majority-kSAT is in P. In fact, for any positive integer k and rational ρ∈(0,1) with bounded denominator, we present an algorithm which determines whether a given k-CNF has at least ρ2^{n} satisfying assignments, in deterministic linear time (whereas the previous best-known algorithm ran in exponential time).
In this talk we give an overview of the main ideas behind these algorithms, and highlight the implications for some additional problems related to counting satisfying assignments.
Seminaire : Séminaire CaNa -- Titouan Carette
02/11/2021 à 14h00
Orateur : Titouan CaretteSalle : TPR2-04.05
Title: ZX-calculus, a Swiss army katana for quantum computing.
Abstract: It usually requires months to master the concepts of quantum mechanics necessary to quantum computing. This time can be reduced drastically by using conveniently designed notations. The ZX-calculus, a graphical language to denote tensor, have been claimed to be such a powerful tool allowing to learn and then reason efficiently on quantum processes. I will support this claim by providing several examples of applications through three extensions of the ZX-calculus that have been introduced in the recent years, namely: mixed states, scalable, and stream ZX-calculus.
Rencontre : Demi-journée pôle calcul - Logique et méthodes formelles
14/10/2021 à 09h30
Lieu : FRUMAMOrateurs :
- Ugo Dal Lago (UniBo) "On Higher-Order Cryptography"
- Pierre Clairambault (LIS) "Games with no Winner: an Introduction to Game Semantics"
- Raphaelle Crubillé (LORIA) “Sémantique dénotationelle pour les languages de programmation probabilistes”
Pour les abstracts, rendez-vous sur le site des demi-journées du pôle : https://demi-journees-pole-calcul.lis-lab.fr
Seminaire : Séminaire CaNa -- Giovanni De Felice
05/10/2021 à 14h00
Salle : TPR2 - 04.05Titre : Quantum Natural Language Processing
Résumé : I will talk about string diagrams, how they are used to capture different models of quantum computation (e.g. circuit-based, measurement-based and linear optical quantum computing), as well as different models of natural language syntax (e.g. context-free grammars, pregroup grammars). I will show how to use this to perform natural language processing on currently available quantum hardware.
Conference : Séminaire DYNI - Luca Tassara - Akvaplan-Niva
29/09/2021 à 14h00
1. Akvaplan-niva: a small Arctic company looking to a bright innovative future. This presentation will focus on the investments and potential of akvaplan-niva on the use and development of unmanned autonomous vehicles. An overview of past,current and future projects involving our glider fleet will be presented 2. Ecological founding from passive acoustic data collected from a sea glider in the norwegian sea. This presentation will focus on the published and preliminary results of acoustic data collected in 2018 by a sea glider off the Lofoten-Vesterålen archipelago. Species presence, occurrence and vocal behaviour will be presented along with a study on the anthropogenic noise recorded in the area.Seminaire : Séminaire de rentrée du pôle SD
23/09/2021 à 10h00
Lieu : St Charles - Salle du séminaire, 2ème étage à la FRUMAM Thème : détection d’anomalies & sciences des données. Présenté par Fidel Cacheda Titre : Early Detection of Anomalies: Presenting a new problem Abstract: In this talk we introduce the Early Detection of Anomalies problem, an area where the Telematics Research group from the University of A Coruña (Spain) has been focusing his work ultimately. Firstly, the research background is introduced and then we present two specific cases of early detection on social networks: early detection of depression and of cyberbullying. From this point, we introduce the generic problem of early detection of anomalies and the ongoing work the research group is developing and the open lines and questions.Conference : Conférence Internationale Francophone sur la Science des Données (CIFSD)
09/06/2021 à 08h00
La Conférence Internationale Francophone sur la Science des Données (CIFSD) est un événement scientifique permettant de réunir à la fois des universitaires et des industriels travaillant en science des données. L'édition 2021 aura lieu du 9 au 11 juin à Marseille (France). En raison de la situation sanitaire actuelle, elle aura lieu intégralement à distance. L’inscription est gratuite mais obligatoire. Cette conférence permet aux chercheurs francophones de présenter leurs travaux et d'échanger leurs idées ; elle donne aussi aux doctorants l'occasion d'appréhender un large panorama sur leur domaine de recherche et de bénéficier d'un premier contact à la fois rigoureux et bienveillant avec l'ensemble des activités liées à la communication scientifique. C’est également l’occasion de nouer des contacts avec d'autres équipes de recherche et des partenaires industriels. Nous encourageons les soumissions d’articles (date limite : 2 avril), qu’il s’agisse de travaux théoriques ou appliqués, sur tous les aspects du cycle de vie de la science des données (le nettoyage et la préparation des données ; la transformation ; l'extraction, l'inférence, l'apprentissage ; la visualisation ; l'explicabilité ; la confidentialité ; etc.). Pour cette édition, les travaux portant sur la science de données pour la santé seront particulièrement appréciés. Plus d'informations sur le site web de la conférence : https://cifsd-2021.sciencesconf.orgConference : Colloque international interdisciplinaire Droit & Sciences : Le bruit en mer : du développement des activités maritimes à la protection de la faune marine
04/06/2021 à 09h00
Vendredi 4 juin 2021Encore peu saisi par les juristes, le bruit en mer lié au développement des activités maritimes versus la protection de la faune marine constitue, depuis plusieurs années, un sujet de recherche à part entière dans le domaine des sciences, notamment au Canada et aux États-Unis. Ce colloque, inédit en France, vise à promouvoir des interactions interdisciplinaires sur fond d’un dialogue constructif entre chercheurs, acteurs économiques, membres de la société civile et autorités administratives en vue de dégager des solutions pour concilier développement des activités maritimes et protection de la faune marine. Un état de la recherche sur le bruit en mer et les effets du trafic maritime sur la faune marine sera tout d’abord dressé pour tenter de mesurer les efforts devant être déployés afin de réduire le bruit anthropique et limiter les impacts sur le milieu marin.
Organisée par des enseignants-chercheurs de l’Université de Toulon membres des laboratoires CDPC, CERC et LIS, avec les soutiens de la Préfecture maritime de la Méditerranée et des pôles INPS et MEDD, cette manifestation se tiendra en présentiel à l’amphithéâtre 300 de la Faculté de droit de Toulon (pour les intervenants uniquement) et en visioconférence (pour les autres participants compte tenu des contraintes sanitaires liées à la Covid-19)
En présentiel pour les intervenants : Amphithéâtre 300 - Faculté de droit de Toulon En ligne pour les autres participants sur inscription (gratuite & obligatoire) : fac.droit@univ-tln.frSeminaire : Séminaire - Yuki Mitsufuji: localisation, classification and separation of acoustic sources
26/05/2021 à 16h00
Yuki Mitsufuji (Member, IEEE) received the B.S. and M.S. degrees in information science from Keio University, Tokyo, Japan, in 2002 and 2004, respectively. He is currently working toward the Ph.D. degree with the University of Tokyo. He is a Deputy General Manager with Speech and Music Group, Sony Corporation, Tokyo, Japan. He has been leading teams that developed the sound design for the PlayStation game title called “Gran Turismo Sport,” and spatial audio solution called “Sonic Surf VR.” In 2004, he joined Audio Technology Development Group, Sony Corporation. From 2011 to 2012, he was a Visiting Researcher with Analysis/Synthesis Team, Institut de Rechereche et Coordination Acoustique/Musique (IRCAM), Paris, France. He was involved in the 3DTV content search project sponsored by European Project FP7, in research collaboration with IRCAM. He is a Reviewer with ICASSP, INTERSPEECH, etc. He currently became a General Chair of Signal Separation Evaluation Campaign where his team had scored the best results for three consecutive years. He has numerous granted patents for audio signal processin Abstract: 1) ACCDOA: Activity-Coupled Cartesian Direction of Arrival Representation for Sound Event Localization and Detection https://arxiv.org/abs/2010.15306 Neural-network (NN)-based methods show high performance in sound event localization and detection (SELD). Conventional NN-based methods use two branches for a sound event detection (SED) target and a direction-of-arrival (DOA) target. The two-branch representation with a single network has to decide how to balance the two objectives during optimization. Using two networks dedicated to each task increases system complexity and network size. To address these problems, we propose an activity-coupled Cartesian DOA (ACCDOA) representation, which assigns a sound event activity to the length of a corresponding Cartesian DOA vector. The ACCDOA representation enables us to solve a SELD task with a single target and has two advantages: avoiding the necessity of balancing the objectives and model size increase. In experimental evaluations with the DCASE 2020 Task 3 dataset, the ACCDOA representation outperformed the two-branch representation in SELD metrics with a smaller network size. The ACCDOA-based SELD system also performed better than state-of-the-art SELD systems in terms of localization and location-dependent detection. 2) D3Net: Densely connected multidilated DenseNet for music source separation https://arxiv.org/abs/2010.01733 Music source separation involves a large input field to model a long-term dependence of an audio signal. Previous convolutional neural network (CNN)-based approaches address the large input field modeling using sequentially down- and up-sampling feature maps or dilated convolution. In this paper, we claim the importance of a rapid growth of a receptive field and a simultaneous modeling of multi-resolution data in a single convolution layer, and propose a novel CNN architecture called densely connected dilated DenseNet (D3Net). D3Net involves a novel multi-dilated convolution that has different dilation factors in a single layer to model different resolutions simultaneously. By combining the multi-dilated convolution with DenseNet architecture, D3Net avoids the aliasing problem that exists when we naively incorporate the dilated convolution in DenseNet. Experimental results on MUSDB18 dataset show that D3Net achieves state-of-the-art performance with an average signal to distortion ratio (SDR) of 6.01 dB.Seminaire : Séminaire Pôle Calcul -- Zoltan Szabo
20/05/2021 à 10h00
Titre : Vector-valued Prediction with RKHSs and Hard Shape ConstraintsAbstract : Shape constraints (such as non-negativity, monotonicity, convexity, or supermodularity) provide a principled way to encode prior information in predictive models with numerous successful applications in econometrics, finance, biology, reinforcement learning, and game theory. Incorporating this side information in a hard way (for instance at all points of an interval) however is an extremely challenging problem. We propose a unified and modular convex optimization framework to encode hard affine SDP constraints on function derivatives into the flexible class of vector-valued reproducing kernel Hilbert spaces (RKHS). The efficiency of the technique is illustrated in the context of joint quantile regression (analysis of aircraft departures), convoy localization, safety-critical control (piloting an underwater vehicle while avoiding obstacles), and econometrics (learning of production functions). This is joint work with Pierre-Cyril Aubin-Frankowski. Preprint: http://arxiv.org/abs/2101.01519
Seminaire : Séminaire I&M - Raphaël Abelé
30/04/2021 à 14h00
Titre : Traitement d'images pour l'automatisation de caractérisation sécuritaire de circuits intégrés.Lieu : Luminy, TPR2 salle de réunion 04.02.
Résumé :
L’automatisation est un enjeu stratégique dans l’industrie. En général, certaines technologies ne peuvent évoluer qu’à condition que la technologie précédente soit parfaitement maîtrisée. Cette maîtrise peut aboutir à lamise en place de procédures automatiques pour des tâches répétitives optimisables.
Dans le contexte très particulier de la caractérisation sécuritaire de circuits intégrés, nous proposons d’automatiser le déplacement du système optique d’un banc d’injection laser. Ce banc est en effet muni d’une caméra infrarouge qui, couplée à un microscope optique, permet d’explorer les entrailles d’une puce électronique. Ce système optique est utilisé à des fins d’analyses, pour étudier le comportement d’un circuit intégré à la suite de perturbations provoquées par des tirs laser localisés sur des points de ses pistes conductrices. Ces tirs sont principalement calibrés et ciblés grâce au système optique.
À travers ce travail, notre objectif est de rendre possible l’automatisation de processus qui requièrent initialement l’intervention humaine. Nous proposons pour cela deux outils dédiés au domaine de la vision infrarouge de circuits intégrés. Des processus tels que le ciblage de structures électroniques d’intérêt pourront être automatisés grâce à ces outils. Dans un premier temps, un processus de mise au point automatique du système optique est présenté, permettant de focaliser les pistes conductrices du circuit intégré, selon des critères propres au contexte. Deux approches sont mises en place, fondées sur l’analyse des images dans le domaine temps-fréquence : une approche passe par une transformée en ondelettes des images, l’autre passe par une transformée polynomiale. Si elles sont toutes deux optimisées pour l’analyse d’images infrarouges, les autofocus qui en découlent ont chacun leur avantage : temps d’exécution pour l’un, précision pour l’autre. Dans un second temps, nous présentons un système de localisation de structures électroniques. Ce système met en œuvre des appariements de graphes et fait intervenir des descripteurs décisifs pour notre application. Dans notre contexte, outre sa robustesse, notre approche tire profit des graphes dans la reconnaissance de formes à partir de simples schématisations.
Le déploiement de ces outils offre des perspectives majeures pour l’amélioration des caractérisations sécuritaires : scans de composants, optimisation et reproductibilité de caractérisation, reconnaissance de composants et de structures ou encore aide à l’interprétation de fautes. De nombreuses pistes sont ouvertes, pour lesquelles la vision par ordinateur est l’élément clé.
Conference : LES LIMITES DE L'INTELLIGENCE ARTIFICIELLE - GRAND SÉMINAIRE - Lundi 26 avril avec YANN LE CUN Prix Turing, Facebook AI Research New York University
26/04/2021 à 16h30
Les laboratoires IMSIC et LIS seront heureux d'accueillir le séminaire du groupe de recherche _ AI Studies_ le lundi 26 avril de 16h30 à 18h00 en visioconférence. Pour interroger les limites de l'intelligence artificielle, tous les participants peuvent contribuer en posant une question lors de l'inscription. Ce lundi 26 avril, nous discuterons avec Yann Le Cun, Prix Turing. https://fr.wikipedia.org/wiki/Yann_Le_Cun Pour accéder à la salle de visioconférence, validez votre inscription pour cette visioconférence exceptionnelle !David Galli, Franck Renucci et Benoît Le Blanc
Seminaire : Séminaire d'équipe LIRICA
26/04/2021 à 14h00
Orateur : Wessley Fussner Titre : Ortholattices résiduels comme nouvelle approche de la logique quantique Résumé : Cet exposé passe en revue nos récentes tentatives d'étudier le raisonnement quantique à l'aide des outils des logiques sous-structurelles. Nous introduisons les ortholattices résiduels comme des modèles algébriques généralisant les modèles habituels de la logique quantique, et illustrons qu'ils donnent une version `intuitioniste' de la logique quantique dans laquelle la logique quantique classique peut être interprétée par une traduction à double négation. Nous discutons également des applications aux problèmes de décidabilité. Lien zoom : Time: Apr 26, 2021 02:00 PM Paris Join Zoom Meeting https://univ-amu-fr.zoom.us/j/8390049740 Meeting ID: 839 004 9740WorkShop : 10th International Workshop Weighted Automata: Theory and Applications
19/04/2021 à 00h00
10th International Workshop Weighted Automata: Theory and Applications WATA 2020/2021 (reported because of the Covid-19) April 19–23, 2021, CIRM@Marseille, France The workshop covers all aspects of weighted automata, ranging from the theory of weighted automata and quantitative logics to applications for real-time systems and natural language processing. The aim is to present tutorials and survey lectures by outstanding scientists in this area. We invite everybody to participate in this workshop without fee and to present their own technical contributions in this area.Rencontre : Saison indécidabilité et impossibilité
08/04/2021 à 14h00
Dans le cadre du séminaire MoVe, une série d'exposés est prévue au cours des années 2019/2020 et 2020/2021 sur les thèmes de l'indécidabilité et de l'impossibilité. Ces exposés font intervenir des orateurs des équipes MoVe, DALGO et ACRO du LIS et des équipes GDAC et LDP de l'I2M.Le programme est disponible sur la page des séminaires de l'équipe MoVe : ICI. Les dernières échéances sont les 11 et 25 février 2021 puis 11 mars 2021 et 8 et 29 avril 2021.
Cette série d'exposés s'inscrit dans le cadre des activités communes du Pôle Calcul du LIS.
Elle est évidemment ouverte aux collègues d'autres équipes/pôles intéressés par ces thèmes.
Seminaire : Séminaire Pôle Calcul -- Olivier Bournez
25/03/2021 à 00h00
Titre : Computations with ordinary differential equationsAbstract : Computability, complexity, programming, continuous time computations, old and recent analog models of computations: Why ordinary differential equations are fun and a pleasant way to do computer science in 2020. Olivier et ses co-auteurs François Fages, Guillaume Le Guludec et Amaury Pouly, ont reçu le prix 2019 du journal La Recherche pour leurs travaux sur les modèles de calcul analogiques et en particulier l’article Strong Turing Completeness of Continuous Chemical Reaction Networks and Compilation of Mixed Analog-Digital Programs. https://www.lemonde.fr/blog/binaire/2019/02/15/la-revanche-du-calcul-analogique/
Seminaire : Séminaire I&M - Marc-Adrien Hostin
26/02/2021 à 14h00
Titre : Méthodes d’apprentissage profond pour la segmentation d’images IRM multiparamétriques musculaires : Suivi et évaluation de stratégies thérapeutiques de pathologies neuromusculaires.Lieu : Luminy, TPR2 salle de réunion 04.02.
Résumé :
Dans le cadre des maladies neuromusculaires, le tissu musculaire est le siège d’un certain nombre d’altérations s’accompagnant de phénomènes inflammatoires, fibrotiques, nécrotiques conduisant à un remplacement progressif du tissu musculaire par des adipocytes et entraînant une perte fonctionnelle. L’imagerie par Résonance Magnétique (IRM) s’est imposée comme un outil de choix pour l’exploration des maladies neuromusculaires [1]. Récemment, des séquences IRM ont permis l’obtention de cartes paramétriques susceptibles de fournir des métriques reliées à l’infiltration graisseuse et à l’inflammation, identifiées comme des biomarqueurs potentiels des maladies neuromusculaires [2]. L’acquisition de ces cartes paramétriques autorise l’étude des neuropathies au travers de scores quantitatifs. Dans ce champ disciplinaire, le défi actuel est de pouvoir fournir des indices quantitatifs fiables et suffisamment sensibles pour pouvoir suivre l’évolution lente de ces pathologies et à terme de déterminer l’efficacité de stratégies thérapeutiques qui sont en cours de développement. Ce challenge nécessite d’une part l’optimisation des méthodes d’acquisition IRM et d’autre part le développement de techniques robustes de segmentation d’images permettant d’associer ces métriques à chaque muscle pris de façon individuelle. En effet, l’utilisation appropriée de cartes paramétriques IRM nécessite de sélectionner l’information sur les zones d’intérêt, les muscles, en ignorant les zones comme la graisse sous-cutanée et l’os. Le défi est d’autant plus relevé que le contraste entre les différents muscles est inexistant et que le contraste de l’infiltrat graisseux pathologique est identique au contraste de la graisse sous-cutanée non pathologique. Les méthodes de segmentation manuelle sont fastidieuses, inapplicables dans un contexte clinique et peuvent être opérateurs-dépendantes [3]. Les méthodes automatiques existantes ne sont pas suffisantes pour prendre en compte la complexité de la tâche de segmentation, particulièrement pour les sujets atteints d’infiltration graisseuse, rendant difficile l’identification des muscles. L’apprentissage profond montre cependant des résultats prometteurs pour les cas les plus atteints, avec l’utilisation de réseaux de convolutions [4].
L’objectif de ce projet est de développer des techniques d’apprentissage profond permettant de segmenter de façon fiable les muscles individuels au niveau d’images IRM de patients atteints de pathologies neuromusculaires. Les résultats de segmentation, donc d’identification des muscles, pourront compléter les différentes cartes paramétriques afin d’extraire pour chaque muscle des indices quantitatifs liés aux maladies neuromusculaires.
Bibliographie :
1. Mercuri E, Pichiecchio A, Allsop J, Messina S, Pane M, Muntoni F. Muscle MRI in inherited neuromuscular disorders: Past, present, and future. Journal of Magnetic Resonance Imaging. 2007;25(2):433-440.
2. Morrow JM, Sinclair CDJ, Fischmann A, et al. MRI biomarker assessment of neuromuscular disease progression: a prospective observational cohort study. The Lancet Neurology. 2016;15(1):65-77.
3. Barnouin Y, Butler-Browne G, Voit T, et al. Manual segmentation of individual muscles of the quadriceps femoris using MRI: a reappraisal. J Magn Reson Imaging. 2014;40(1):239-247. doi:10.1002/jmri.24370.
4. Gadermayr M, Disch C, Müller M, Merhof D, and Gess B. A comprehensive study on automated muscle segmentation for assessing fat infiltration in neuromuscular diseases. Magnetic resonance imaging 2018 ;48:20–26.
Seminaire : Séminaire Pôle Calcul -- Vincent Nozick
18/02/2021 à 10h00
Le séminaire aura lieu en visioconférence, pour obtenir les identifiants de connexion merci de vous adresser à Nathanaël Eon : nathanael.eon@lis-lab.frTitre : Introduction aux Algèbres Géométriques et leur aspects calculatoires
Abstract : Les Algèbres Géométriques constituent un ensemble d'outils intuitifs permettant de créer et de manipuler des objets géométriques. Longtemps entre les mains des mathématiciens, les informaticiens commencent à se les approprier et à entrevoir leur potentiel. Cet exposé s'inscrit dans cette démarche d'explication simple et commencera par une introduction sur les fondements de ces algèbres, à savoir les vecteurs, les multivecteurs ainsi que quelques produits sur ces multivecteurs. Nous verrons ensuite comment les utiliser pour résoudre efficacement et très simplement des problèmes de géométrie, en portant une attention particulière sur l'aspect calculatoire.
Seminaire : Séminaire CaNa - Amélia Durbec
16/02/2021 à 14h00
Oratrice : Amélia DurbecTitre : Classical and quantum causal graph dynamics
Abstract : Causal graph dynamics are a twofold extension of cellular automata : the underlying grid is extended to an arbitrary bounded-degree graph and the graph itself is allowed to evolve over time. Such dynamics are insightful toy models for theoritical physics in both the reversible and the quantum regime. In this talk, we are going to see how a graph dynamics can be reversible and yet create/destroy vertices, and that vertex names are necessary in order to prevent faster-than-light signalling. We will finish this talk with outlooks towards graph self-assembly and graph subshifts.
Seminaire : Séminaire Pôle Calcul -- François Le Gall
28/01/2021 à 10h00
Le séminaire aura lieu en visioconférence, pour obtenir les identifiants de connexion merci de vous adresser à Nathanaël Eon : nathanael.eon@lis-lab.frTitre : Quantum Distributed Computing
Abstract : The subject of this talk will be quantum distributed computing, i.e., distributed computing when the processors of the network can exchange quantum information. After describing the basics of both classical distributed computing and quantum computing, I will explain a result obtained with Frédéric Magniez (PODC 2018) on quantum distributed algorithms computing the diameter of the network. I will then briefly present more recent results (STACS 2019, PODC 2019) that show a separation between the computational powers of quantum and classical distributed algorithms in other models as well. I will conclude my talk by mentioning interesting and important open questions in quantum distributed computing.
Seminaire : Séminaire MOVE : Karoliina Lehtinen (LIS), Between determinism and nondeterminism, what are good-for-games automata good for?
22/01/2021 à 14h00
Luminy, Salle de réunion 5.37 TPR2 Titre : Between determinism and nondeterminism, what are good-for-games automata good for? Résumé : Nondeterminism probably makes your favourite automata model more expressive, or at least more succinct, than determinism. However, nondeterminism comes with higher algorithmic complexity. Good-for-games automata, also known as history deterministic automata, lie in between deterministic and nondeterministic models, trying to salvage some of the expressivity and succinctness of nondeterminism, without giving up on the nice algorithmic properties of deterministic automata. In this talk, I will give an overview of good-for-games automata, survey recent developments in the area for regular, pushdown and timed automata, and point to some of the hard questions that remain unanswered and some areas that remain unexplored.Seminaire : Séminaire CaNa - répétition ouverte de la soutenance de thèse de Pacôme Perrotin
05/01/2021 à 14h00
Orateur : Pacôme PerrotinTitre : Simulation entre modèles de calcul naturel et modularité des réseaux d'automates
Lieu : contacter par mail Nathanaël Eon pour obtenir le lien de la visioconférence.
Résumé : Nous explorons différentes généralisations concernant les modèles de calcul naturel. La plus théorique est la notion de simulation entre modèles, pour laquelle nous décrivons une série de propositions de définition, en discutant des intérêts et des failles de chacune d'elles. Nous profitons des définitions les plus prometteuses pour élargir le propos sur les possibles conséquences de la simulation en théorie de la complexité, comme la construction de nouvelles classes de complexité en proposant la substitution de la réduction polynomiale par la simulation. Notre approche plus appliquée consiste en la généralisation des réseaux d'automates sous formes de modules, qui possèdent des entrées. Ce formalisme permet d'approcher les questions de la dynamique des réseaux d'interactions sous un nouvel angle : nous explorons son utilité en tant qu'outil modulaire propre à simuler de façon flexible de nombreux objets similaires, ainsi que l'expressivité des modules acycliques. Ceux-ci permettent la caractérisation de la dynamique des réseaux d'automates sous la forme de fonctions de sortie. Cette expressivité nous autorise la description d'un processus d'optimisation de réseaux d'automates, qui réduit certains réseaux en taille tout en conservant des attracteurs équivalents.
Seminaire : Séminaire MOVE : Ismaël Jecker (IST Austria)
17/12/2020 à 10h30
Prime languages A regular language L of finite words is composite if there are regular languages L1, L2, . . . , Lt such that L is equal to the intersection of the Li, and the index (number of states in a minimal DFA) of every language Li is strictly smaller than the index of L. Otherwise, L is prime. This notion of primality was introduced by Orna Kupferman and Jonathan Mosheiff in 2015, and the complexity of deciding the primality of the language of a given DFA was left open, with a doubly-exponential gap between the upper and lower bounds. In this talk, I will present some recent results concerning primality in some subclasses of regular languages. First, we will consider unary regular languages, namely regular languages with a singleton alphabet. A unary language can be interpreted as a set of positive integers, making the study of prime unary languages close to that of primality in number theory. We will see that the setting of languages is richer. In particular, while every composite number is the product of two smaller numbers, the number t of languages necessary to decompose a composite unary language induces a strict hierarchy. In addition, a primality witness for a unary language L, namely a word that is not in L but is in all products of languages that contain L and have an index smaller than L’s, may be of exponential length. Still, we are able to characterize compositionality by structural properties of a DFA for L, leading to a LogSpace algorithm for checking primality of unary DFAs. Second, I will present our (ongoing) work on regular languages definable by permutation DFAs, namely DFAs whose transition monoid is a group. We will see that, while we cannot apply the exact same techniques used in the unary setting, they can be adapted to obtain an NP algorithm checking primality of permutation DFAs, improving the previously known PSpace algorithm.Seminaire : Séminaire MOVE : Marie Fortin (University of Liverpool)
15/12/2020 à 10h30
Expressivity of first-order logic, star-free propositional dynamic logic and communicating automata This talk is concerned with the expressive power of first-order logic and other formalisms over different classes of ordered structures, among which MSCs (Message Sequence Charts), a standard model for executions of message-passing systems. This study is motivated by two classic problems: the k-variable property, that is, the equivalence of first-order logic and its k-variable fragment over certain classes of structures, and the study of logic-automata connections, in the spirit of Bütchi-Elgot-Trakhtenbrot theorem. Our approach relies on star-free propositional dynamic logic (star-free PDL), a variant of PDL with the same expressive power as the 3-variable fragment of first-order logic. We start by studying the expressive power of star-free PDL over linearly ordered structures with unary and binary predicates. We show that under certain monotonicity conditions, star-free PDL becomes as expressive as first-order logic. This implies that any first-order formula can then be rewritten into an equivalent formula with at most 3 variables. This result applies to various natural classes of structures, generalizing several known results and answering some open questions. We then focus on MSCs, to which this first result also applies. We use star-free PDL to address another important problem: the synthesis of communicating finite-state machines (CFMs) from first-order specifications. CFMs are a model of concurrent systems in which a fixed number of finite-state automata communicate through unbounded FIFO channels. They accept languages of MSCs. While logical characterizations of the expressive power of CFMs have been established under different restrictions (bounding the size of the communication channels, or removing the "happened-before" relation from the logic), the following question had remained open in the general case: can every first-order formula over MSCs be translated into an equivalent CFM? We prove that this is the case, using star-free PDL as an intermediate language.Seminaire : Séminaire MOVE : Engel Lefaucheux (Max-Planck Institute for Software Systems, Sarrebrucken), On the Monniaux Problem in abstract interpretation
08/12/2020 à 14h00
On the Monniaux Problem in abstract interpretation The Monniaux Problem in abstract interpretation asks, roughly speaking, whether the following question is decidable: given a program P, a safety (e.g., non-reachability) specification φ, and an abstract domain of invariants D, does there exist an inductive invariant in D guaranteeing that program P meets its specification φ. The Monniaux Problem is of course parameterised by the classes of programs and invariant domains that one considers. In this talk, I’ll present a select overview and survey of work on this problem, and discuss some recent results for semilinear invariants for unguarded affine programs. Séminaire en visioSeminaire : Séminaire MOVE : Léo Exibard (LIS), Computability and Continuity of Data Word Functions Defined by Transducers
30/11/2020 à 14h00
Computability and Continuity of Data Word Functions Defined by Transducers Last year, Dave, Filiot, Krishna and Lhote established an equivalence between the notions of continuity and computability for functions over infinite (aka omega-) words[*]. In this talk, we extend the study to the case of an infinite alphabet, i.e. to the problem of synthesizing computable functions over data omega-words. The notion of computability is defined through Turing machines with infinite inputs which can produce the corresponding infinite outputs in the limit. We use non-deterministic transducers equipped with registers, an extension of register automata with outputs, to specify functions. Such transducers may not define functions but more generally relations of data omega-words, and we show that it is PSpace-complete to test whether a given transducer defines a function. Then, given a function defined by some register transducer, we show that it is decidable (and again, PSpace-complete) whether such function is computable. As for the finite alphabet case, we show that computability and continuity coincide for functions defined by register transducers, and show how to decide continuity. [*] Nathan presented those results at the MoVe seminar last september, but this talk will be self-contained. Séminaire en visio zoomSeminaire : Séminaire du pôle calcul par Catuscia Palamidessi
26/11/2020 à 10h00
Le séminaire aura lieu en visioconférence, pour obtenir les identifiants de connexion merci de vous adresser à Nathanaël Eon : nathanael.eon@lis-lab.frTitre : A new mechanism for distributed Differential Privacy
Abstract : Differential Privacy (DP) is one of the most successful proposal to protect the privacy of the sensitive data while preserving their utility. In this talk, we will briefly introduce the DP framework, and then present a new proposal for a mechanism to implement DP in the distributed case, namely in a scenario in which the data collections are distributed across different organizations, which do not wish to disclose the original data but only their sanitized version, and still benefit from the advantages of combining the information coming from different sources. The mechanism we propose is particularly suitable for the application of a variant of the statistical Expectation-Maximization method, thanks to which the utility of the original data can be retrieved to an arbitrary degree of approximation, without affecting the privacy of the original data owners.
Seminaire : Séminaire MOVE : Guillaume Maurras (LIS), Caractérisation logique de langages d'ordre supérieur - introduction
23/11/2020 à 14h00
Caractérisation logique de langages d'ordre supérieur - introduction 1/ Büchi : la déterminisabilité des automates finis est l'élément clé de la réciproque 2/ Les langages algébriques : i/ les automates à Pile ne sont pas déterminisables, par contre Alur introduit les NWA (déterminisables) qui permettent un argument "à la Büchi" pour montrer que les modèles de ExistMatchMSO sont exactement les langages algébriques. ii/ conclusion : en enrichissant la structure des mots (d'un couplage) et en construisant une classe d'automates déterminisable (les NWA) on a caractériser logiquement une classe de langage (les algébriques) 3/ Les langages indexés : on voudrait appliquer (ii) on enrichit la structure de mot de 2 couplages (se répondant l'un l'autre d'une certaine façon qu'on appelle "haricot"), on a définit des automates sur ces mots enrichis et prouvés qu'ils sont déterminisables on voudrait catégoriser logiquement la partie (?) des indexés à laquelle ils correspondent. exemple : le langage uu où u est de longueur paire est un langage de "haricot" / un langage indexé Séminaire par visio zoomSeminaire : Séminaire CaNa, Guilhem Gamard (LIS), Rice-like theorems for automata networks
10/11/2020 à 14h00
An automata network (AN for short) is a finite digraph where each node holds a state, choosen among a finite set, that evolves in function of the states of its inbound neighbors. Time is discrete and all nodes evolve synchronously and in parallel, similarly to what happens in an cellular automaton. In other terms, the differences between a cellular automaton and an automata network is that the "grid" is an arbitrary finite digraph, and that different nodes may have different update functions. ANs have been used to model neural networks, dynamics of expression and inhibition of genes, distributed algorithms, and more. Although ANs look like a model of computation, they are not Turing-complete, for they lack unbounded memory. Still, they are subject to some kind of "Rice theorems", i.e., results along the lines of: "any nontrivial property of the function computed by an automata network is computationally hard to test". In this talk, we will review several results that fit this pattern, as well as pieces of proof that hopefully may be reused in other contexts.Seminaire : Séminaire MOVE : Louis-Marie Dando (LIS), Les automates circulaires sur les rationnels
05/11/2020 à 10h30
Les automates circulaires sur les rationnels Dans cet exposé, je vous présenterai quelques résultats obtenus durant ma thèse. Le premier est que sur les semi-anneaux rationnellement additifs (et on peut étendre aux rationnels), les automates circulaires et les expressions de Hadamard réalisent les mêmes séries. Ce résultat est constructif. Le second résultat est que l'on peut transformer un automate two-way en un automate circulaire sur Q. Lieu : salle de réunion LIS, LuminySeminaire : Séminaire MOVE : Charles Paperman (Université de Lille), Stackless processing of streamed trees
21/10/2020 à 14h00
Stackless processing of streamed trees In this talk I will first present the state of the art of efficiency implementation of streaming-text algorithms on modern architecture. Then some recent results on the extraction of information on streamed of structured documents without stack overhead. Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), LuminySeminaire : Séminaire du pôle calcul par Adrien Varet
15/10/2020 à 10h00
Le séminaire aura lieu en visioconférence, pour obtenir les identifiants de connexion merci de vous adresser à Nathanaël Eon : nathanael.eon@lis-lab.frLes benzénoïdes sont une sous-famille des hydrocarbures (molécules uniquement constituées d'atomes de carbone et d'hydrogène) dont les atomes de carbones forment des hexagones. Ces molécules sont beaucoup étudiées en chimie théorique. En effet, il existe un certain nombre de problèmes relatifs aux benzénoides dans différents domaines. Dans cette présentation, on se propose de se pencher sur deux problématiques en particulier, qui sont être capable de générer des structures de benzénoïdes ou calculer l'aromaticité locale d'un benzénoïde donné. Calculer l'aromaticité locale d'un benzénoïde revient à attribuer une énergie à chacun de ses hexagones qui est induite par les déplacements de ses électrons. A l'heure actuelle, la méthode la plus utilisée pour faire ce calcul (appellée NICS) requiert des calculs de chimie quantique et est extrêmenent coûteuse. Dans cette présentation, j'aborderais dans un premier temps une méthode utilisant la programmation par contraintes capable de générer l'ensemble de structures de benzénoïdes répondant à un certain nombre de de propriétés (qui peuvent être chimiques ou structurelles). Dans un second temps, je présenterais un algorithme utilisant la programmation par contraintes capable de calculer l'aromaticité locale d'un benzénoïde donné.
Seminaire : Séminaire MOVE : Benjamin Monmege (LIS), Dynamics on Games (2): Simulation-Based Techniques and Applications to Routing
08/10/2020 à 10h30
We consider multi-player games played on graphs, in which the players aim at fulfilling their own (not necessarily antagonistic) objectives. In the spirit of evolutionary game theory, we suppose that the players have the right to repeatedly update their respective strategies (for instance, to improve the outcome w.r.t. the current strategy profile). This generates a dynamics in the game which may eventually stabilise to an equilibrium. The talk will start with a short presentation of evolutionay game theory. Then, I will present our twofold contribution. First, we aim at drawing a general framework to reason about the termination of such dynamics. In particular, we identify preorders on games (inspired from the classical notion of simulation between transitions systems, and from the notion of graph minor) which preserve termination of dynamics. Second, we show the applicability of the previously developed framework to interdomain routing problems. This is a joint work with Thomas Brihaye, Gilles Geeraerts, Marion Hallet and Bruno Quoitin. Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), LuminySeminaire : Séminaire CaNa, Antonio E. Porreca (LIS), The semiring of dynamical systems
06/10/2020 à 14h00
We introduce an algebraic approach for the analysis and composition of finite, discrete-time dynamical systems in terms of the category-theoretical operations of sum (disjoint union) and (tensor) product, which correspond to alternative and synchronous execution. This defines a semiring structure over the set of dynamical systems (modulo isomorphism), which allows us to express decomposition problems in terms of factorisation and polynomial equations. We analyse the algebraic properties of the semiring and prove that most dynamical systems are irreducible, and that the reducible ones sometimes admit multiple factorisation into irreducibles. We also prove that polynomial equations over this semiring are, in general, algorithmically unsolvable, and that many solvable subclasses of equations, including linear ones, are intractable even if the explicit dynamics of the systems is given as input (while in applications, where the dynamical systems are described more succinctly, these problems are conjecturally even harder). Finally, we also analyse dynamical systems in terms of their “topographic profiles”, a more abstract view in terms of the number of states at a given distance from the limit cycles of the system, which turns out to share many of the same algebraic properties.Lien pour visionner ce séminaire : https://amupod.univ-amu.fr/video/7228-seminaire-cana-antonio-e-porreca-the-semiring-of-dynamical-systems/
Lien vers les slides : https://aeporreca.org/talks/semiring-of-dynamical-systems.pdf
Seminaire : Séminaire MOVE : Benjamin Monmege (LIS), Dynamics on Games (1): Matrix game theory vs evolutionary game theory
01/10/2020 à 10h30
We consider multi-player games played on graphs, in which the players aim at fulfilling their own (not necessarily antagonistic) objectives. In the spirit of evolutionary game theory, we suppose that the players have the right to repeatedly update their respective strategies (for instance, to improve the outcome w.r.t. the current strategy profile). This generates a dynamics in the game which may eventually stabilise to an equilibrium. The talk will start with a short presentation of evolutionay game theory. Then, I will present our twofold contribution. First, we aim at drawing a general framework to reason about the termination of such dynamics. In particular, we identify preorders on games (inspired from the classical notion of simulation between transitions systems, and from the notion of graph minor) which preserve termination of dynamics. Second, we show the applicability of the previously developed framework to interdomain routing problems. This is a joint work with Thomas Brihaye, Gilles Geeraerts, Marion Hallet and Bruno Quoitin. Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), LuminySeminaire : Séminaire MOVE : Julie Parreaux (LIS), Reaching Your Goal Optimally by Playing at Random with no Memory
24/09/2020 à 10h30
Shortest-path games are two-player zero-sum games played on a graph equipped with integer weights. One player, that we call Min, wants to reach a target set of states while minimising the total weight, and the other one has an antagonistic objective. This combination of a qualitative reachability objective and a quantitative total-payoff objective is one of the simplest settings where Min needs memory (pseudo-polynomial in the weights) to play optimally. In this article, we aim at studying a tradeoff allowing Min to play at random, but using no memory. We show that Min can achieve the same optimal value in both cases. In particular, we compute a randomised memoryless ε-optimal strategy when it exists, where probabilities are parametrised by ε. We also show that for some games, no optimal randomised strategies exist. We then characterise, and decide in polynomial time, the class of games admitting an optimal randomised memoryless strategy. This is a joint work with Benjamin Monmege and Pierre-Alain Reynier. Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), LuminySeminaire : Séminaire MOVE : Nathan Lhote (LIS), Continuity and computability of regular functions
10/09/2020 à 10h30
Regular functions from infinite words to infinite words can be equivalently specified by MSO-transducers, streaming omega-string transducers as well as deterministic two-way transducers with look-ahead. In their one-way restriction, the latter transducers define the class of rational functions. Even though regular functions are robustly characterised by several finite-state devices, even the subclass of rational functions may contain functions which are not computable ((by a Turing machine with infinite input). This paper proposes a decision procedure for the following synthesis problem: given a regular function f (equivalently specified by one of the aforementioned transducer model), is f computable and if it is, synthesize a Turing machine computing it. For regular functions, we show that computability is equivalent to continuity, and therefore the problem boils down to deciding continuity. We establish a generic characterisation of continuity for functions preserving regular languages under inverse image (such as regular functions). We exploit this characterisation to show the decidability of continuity (and hence computability) of rational and regular functions. For rational functions, we show that this can be done in NLogSpace (it was already known to be in PTime by Prieur). In a similar fashion, we also effectively characterise uniform continuity of regular functions, and relate it to the notion of uniform computability, which offers stronger efficiency guarantees. Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), LuminySeminaire : Séminaire du pôle calcul par Adrian Vladu "Graph Algorithms Through the Lens of Continuous Optimization"
03/07/2020 à 14h00
Recent years have witnessed a surge in the development of fast graph algorithms based on continuous optimization primitives. Classically, graph algorithms have relied on purely combinatorial techniques. However, new ideas stemming from Scientific Computing and Machine Learning set forth an emerging theme of algorithm design via continuous optimization.I will provide a tour through some of the techniques that underlie this theme, and show how they can be used to obtain fast algorithms for solving a range of fundamental problems such as: maximum flow, minimum cost flow, or optimal transport with entropic regularization.
This talk is based on arXiv:1902.06391, arXiv:2003.04863, and arXiv:1704.02310, but will be kept self-contained, and will assume no prior background in optimization.
Seminaire : Séminaire CaNa -- Molecular computers in artificial chemistry, Marius Buliga
14/04/2020 à 14h00
Conference : Conférence MachineLearning@LIS
02/04/2020 à 09h00
À l'occasion de la conférence ML@LIS qui aura lieu le 2 Avril à St Jérôme, les chercheurs du Laboratoire d'Informatique et Systèmes feront des présentations scientifiques sur leur travaux de recherche ayant attrait aux aspects théoriques, techniques ou applicatifs du Machine Learning. L'objectif de cette conférence est double: d'abord animer la vie interne du laboratoire, faire en sorte que nous découvrions ce qui se fait dans les différentes équipes, nouer des liens et peut-être même ouvrir la porte à des collaborations si les discussions vont bon train; ensuite, donner un aperçu de ce qui se fait en Machine Learning au LIS pour les spectateurs extérieurs. Cette conférence est gratuite et ouverte sur inscription à toute personne du LIS ou de l'extérieur intéressée par le Machine Learning. Retrouvez toutes les informations sur le site de la conférence: https://mlatlis.lis-lab.fr/.Seminaire : Séminaire MOVE : Adrien Le Coënt (ENSTA Paris, U2IS)
23/03/2020 à 10h30
Adrien Le Coënt (ENSTA Paris, U2IS) Lundi 23 mars, 10h30 Salle de réunion BU1, Luminy Guaranteed simulation and control synthesis for switched systems Switched systems constitute a sub-class of hybrid systems, and the synthesis problem for such systems is still an important issue, particularly when considering safety critical systems. Control synthesis for switched systems has been extensively studied in the past years. One of the current major approaches is symbolic methods, which basically aim at representing the continuous and infinite state-space of the system with a finite number of symbols, e.g. discrete points, sets of states, etc. This type of approaches is particularly adapted for safety critical systems, since it exhaustively ensures that an interest set is safe. However, their computational complexity is usually exponential with the dimension of the system and the fineness of the discretisation. We present some recent results and ongoing work allowing to overcome some of the flaws of the current symbolic methods, relying on guaranteed numerical schemes, abstraction methods and compositional approaches.Seminaire : Séminaire MOVE : Matthieu Rosenfeld (LIS)
19/03/2020 à 10h30
Matthieu Rosenfeld (LIS) Jeudi 19 mars, 10h30 Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy Titre: Calculer le taux de croissance dans les arbres des ensembles définissables en logique monadique du second ordre Un résultat récent de Rote montre que le nombre d'ensembles dominants minimaux dans les arbres d'ordre $n$ est au plus $95^{\frac{n}{13}}$ et que cette borne est optimale. En généralisant les idées qu'il a utilisé on peut montrer qu'on peut calculer algorithmiquement de telles bornes pour tout type d'ensemble définissable en logique monadique du second ordre. En toute généralité, l'algorithme qu'on obtient nous permet d'approximer par le haut la borne optimale. La question de savoir si on peut aussi l'approximer par le bas et donc si ce nombre est calculable reste ouverte. Cependant, en pratique, dans un certain nombre de cas intéressants on arrive a obtenir la valeur exacte (exprimée sous forme de racine d'un polynôme). La méthode utilisée consiste à calculer "le taux de croissance" du langage d'un automate d'arbre. Je commencerai dans mon exposé par m’intéresser à la même question, mais en remplaçant "arbres d'ordre n" par "chemin d'ordre n" pour illustrer certaines idées. Je m'attaquerai ensuite aux difficultés supplémentaires liés aux arbres avant de mentionner plusieurs généralisations.Seminaire : Séminaire MOVE : Vadim Malvone (Université d'Évry)
16/03/2020 à 10h30
Vadim Malvone (Université d'Évry) Lundi 16 mars, 10h30 Salle de réunion BU1, Luminy Raisonnement stratégique en théorie des jeux La théorie des jeux en intelligence artificielle est un puissant cadre mathématique largement appliqué au cours des trois dernières décennies pour le raisonnement stratégique dans les systèmes multi-agents. Les travaux fondateurs sur cette ligne de recherche ont commencé avec des jeux à deux joueurs au tour par tour (sous des informations parfaites et imparfaites) pour vérifier l'exactitude d'un système par rapport à un environnement imprévisible. Ensuite, de gros efforts ont été consacrés à étendre ces travaux au cadre multi-agents et, en particulier, au raisonnement efficace sur les concepts de solution importants tels que l'équilibre de Nash et similaires. Des contributions révolutionnaires dans ce sens concernent l'introduction des logiques pour le raisonnement stratégique telles que la logique temporelle à temps alterné (ATL), la logique stratégique (SL) et leurs extensions. Les jeux à deux joueurs et les logiques pour le raisonnement stratégique sont aujourd'hui des domaines de recherche très actifs. Dans cet exposé, nous présenterons nos contributions dans ces deux axes de recherche.Seminaire : Séminaire MOVE : Célia Borlido (Université de Coimbra)
05/03/2020 à 10h30
Célia Borlido (Université de Coimbra) Jeudi 5 mars, 10h30 Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy Stone Duality and the Substitution Principle Fragments of first-order logic defining regular languages of words can be studied inductively via the so-called “Substitution Principle”. Through this principle, one is able to study logic fragments by successively adding a layer of quantifiers, which is in turn algebraically modeled by the semidirect product of suitable monoids. In this talk we will see that, by interpreting the “Substitution Principle” from the standpoint of Stone duality, one is able to extend it beyond regularity and obtain topo-algebraic counterparts for classes of languages defined by arbitrary first-order logic fragments. As in the regular setting, applying a layer of quantifiers is modeled by a semidirect product construction for suitable recognizers. Such recognizers were proposed by Gehrke, Grigorieff and Pin in 2010 as the topo-algebraic objects to handle not-necessarily regular languages, and they generalize the classical finite and profinite monoids. This is based on joint work with Czarnetzki, Gehrke and Krebs. All concepts related to Stone duality will be introduced during the talk.Seminaire : Séminaire CaNa --Preuve du paradoxe de Banach-Tarski, Kévin Perrot
18/02/2020 à 13h30
Seminaire : Séminaire MOVE : Mathias Ramparison (Université de Luxembourg)
13/02/2020 à 10h30
Mathias Ramparison (Université de Luxembourg) Jeudi 13 février, 10h30 Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy Updatable Parametric Timed Automata: Decidability, Algorithms, and Application to Security As cyber-physical systems become more and more complex, human debugging is not sufficient anymore to cover the huge range of possible behaviours. For costly critical systems where human lives can be endangered, formally proving the safety of a system is even more crucial. This is done by defining a formal specification for the system, and then performing the algorithmic verification that the system satisfies some formally specified properties. With this precise and exhaustive description of a system, the usual vagueness of human language is eliminated. We focus on the verification of timed concurrent systems. Timed-dependent systems are very hard to verify, especially when the exact value of timing constants remains unknown. These unknown timing constants are called parameters. We study several subclasses of a parametric extension of the well-known formalism called Timed Automata. We mainly focus on the reachability decision problem, that asks whether there exists concrete values for these parameters such that a bug state can be reached in the system. We further address for these subclasses a computation problem that is to synthesise the set of parameter values for which a state is reachable. Finally, we apply our work to the security and safety of cyber-physical systems and infrastructure: we extend with parameters a classic formalism to model attack and failure scenarios called attack-fault trees, and propose an implementation of the translation of parametric attack-fault trees to parametric timed automata. This allows us to leverage the verification techniques and tools available for the latter for the analysis of (parametric).Seminaire : Séminaire MOVE : Maria Emilia Descotte (LaBRI, Université de Bordeaux)
16/01/2020 à 10h30
Synchronized word relations A natural approach to defining binary word relations over a finite alphabet A is through two-tape finite state automata, which can be seen as regular languages L over {1,2}xA, where (i,a) is interpreted as reading letter a from tape i. Thus, a word w of the language L denotes the pair (u_1,u_2) in A*xA* in which u_i is the projection of w onto i-labelled letters. While this formalism defines the well-studied class of Rational relations (a.k.a. non-deterministic finite state transducers), enforcing restrictions on the reading regime from the tapes, that we call synchronization, yields various sub-classes of relations. Such synchronization restrictions are imposed through regular properties on the projection of the language onto {1,2}. In this way, for each regular language C over the alphabet {1,2}, one obtains a class Rel(C) of relations, such as the classes of Regular, Recognizable, or length-preserving relations, as well as (infinitely) many other classes. During the talk, we will introduce the formalism of synchronized relations along with its basic properties without assuming any previous knowledge about it. Then we will give the main ideas for the proof of several recent results on the subject. To begin, we will discuss the problem of containment for synchronized classes of relations: given C,D regular languages over the alphabet {1,2}, is Rel(C) a subset of Rel(D)? We will show a characterization in terms of C and D which gives a decidability procedure to test for class inclusion. Then we will move to the problem of deciding whether a given class of synchronized relations is closed under paradigmatic operations such as intersection, complement, etc. We will prove the decidability of these problems by giving a characterization of the classes that are indeed closed under those operations. We will finally make a link between these closure properties and classical problems within the theory of transducers. Only basic knowledge about automata theory will be required. Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), LuminySeminaire : Séminaire CaNa -- Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding Model, Nicolas Schabanel
07/01/2020 à 14h00
Seminaire : Séminaire du Pôle ACS : Patrick Siarry
19/12/2019 à 14h00
salle des commissions, St. JérômeSeminaire : Séminaire du Pôle ACS : Michel Zasadzinski
18/12/2019 à 14h00
Salle des commissions, St. JérômeSeminaire : Séminaire CaNa -- Algebra, Tilings and Nivat, Etienne Moutot
04/12/2019 à 10h30
Seminaire : Séminaire MOVE : Engel Lefaucheux (Max-Planck Institute for Software Systems, Sarrebrucken)
28/11/2019 à 10h30
Engel Lefaucheux (Max-Planck Institute for Software Systems, Sarrebrucken) Jeudi 28 novembre, 10h30 Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy Opacity of a Stochastic System : Maximisation versus Minimisation This talk explores opacity questions where an observation function provides to an external attacker a view of the states along executions and secret executions are those visiting some state from a fixed subset. Disclosure occurs when the observer can deduce from a finite observation that the execution is secret. In a probabilistic and non deterministic setting, where an internal agent can choose between actions, there are two points of view, depending on the status of this agent: the successive choices can either help the attacker trying to disclose the secret, if the system has been corrupted, or they can prevent disclosure as much as possible if these choices are part of the system design. In the former situation, corresponding to a worst case, the disclosure value is the supremum over the strategies of the probability to disclose the secret (maximisation), whereas in the latter case, the disclosure is the infimum (minimisation). I will consider both quantitative problems (comparing the optimal value with a threshold) and qualitative ones (when the threshold is zero or one) for a fixed or a finite horizon and discuss the strange asymmetry existing between maximisation and minimisation problems.Seminaire : DALGO: Jérémie Chalopin (LIS), vendredi 22 novembre à 10h30. Schémas de compression pour les classes maximums et amples.
22/11/2019 à 10h30
Titre : Schémas de compression pour les classes maximums et amples.Orateur: Jérémie Chalopin
Lieu : salle de réunion du LIS, Luminy (Préfabriqué)
Résumé:
Dans cet exposé, je parlerai des connections qui existent entre des questions venant de la théorie de l'apprentissage et des concepts étudiés en géométrie et en théorie métrique des graphes. Après avoir expliqué tous les mots du titre de l'exposé, je présenterai un contre-exemple issu de la géométrie qui montre que les constructions existantes de schémas de compressions pour les classes maximums sont erronées. Je présenterai ensuite une preuve de l'existence de ces schémas de compression pour les classes maximums ainsi que des pistes pour pouvoir généraliser ce résultat aux classes amples.
Travail réalisé avec V. Chepoi, S. Moran et M. K. Warmuth. https://arxiv.org/abs/1812.02099
Seminaire : Séminaire Pole ACS - Yacine Chitour: "Finite time stabilization for chains of integrators" - 21/11/2019 - 14h - St Jérôme
21/11/2019 à 14h00
Yacine Chitour: "Finite time stabilization for chains of integrators"
21 novembre 2019, 14h, St. Jérôme, Salles des commissionsYacine Chitour, L2S-CentraleSupélec
- Titre: Finite time stabilization for chains of integrators
- Abstract: In this talk, I will present various technics of stabilization in finite time for perturbed and unperturbed chains of integrators. These issues arise in sliding mode control. Joint work with M Harmouche and S Laghrouche
https://pole-acs.lis-lab.fr/
Conference : 4ème Demi-journée Pole Calcul - Intelligence Artificielle - 21 novembre
21/11/2019 à 09h30
Dans le cadre du deuxième cycle des demi-journées du Pole Calcul du LIS, la prochaine sera autour du thème “Intelligence Artificielle”, organisée le jour 21 novembre 9h30 à 12h30 dans la salle des séminaires au 2ème étage du FRUMAM de Saint Charles. Les trois intervenants confirmés sont Hans van Ditmarsch, Loria, Vincent Risch (LIS) et notre thésard Tiziano Dalmonte (LIS).Quatrième demi-journée (“Intelligence Artificielle”) 21 Novembre
(45min each + 10 mins questions + 15 min coffe break)
9h30 -> 10h15 —Tiziano Dalmonte, LIS
Titre: Non-normal modal logics: from models to proofs
Abstract: Modal logics are applied in many different contexts, such as epistemic, deontic or temporal reasoning, and many others. In some of these contexts, the minimal normal modal logic K leads to counter-intuitive conclusions, such as the problem of logical omniscience or the problem of conflicting obligations, and gives rise to several paradoxes (Ross paradox, the paradox of gentle murder, …). For this reason, weaker modal logics -- called non-normal – are considered. Non-normal modal logics are traditionally characterised by a possible world semantics with a neighbourhood function. In this talk I present an alternative semantics which is more natural for systems lacking monotonicity. I also present some new proof systems which have 'good' properties, moreover they provide a decision procedure of optimal complexity and allow one to construct countermodels for non-valid formulas. In the final part I present some open problems.
10h25 -> 11h10 — Vincent Risch (LIS)
Titre: Consistency Measures, Inconsistency Measures, and Mix Measures (Preliminary Report)
En collaboration avec Philippe Besnard
Abstract: We give some insight into a preliminary attempt at investigating
a notion of consistency measures. These would provide
a consistency degree for any finite collection of logical
formulas, on a par with the well-known notion of inconsistency
measures, that aim at assigning degrees of inconsistency to
finite sets of logical formulas. We first propose a basic set
of postulates for consistency measures. We look at a couple
of relationships with inconsistency measures. We even lay
grounds for a formal duality between these two domains.
Lastly, we have a look at what would be a mix measure,
that is, a measure that gives a degree, on the same scale,
for consistency (positive values) and inconsistency (negative
values). We also mention supermodels, as defined by
Ginsberg et al., as well as a theory that can be regarded
as a generalization of super-models, namely morpho-logics.
11h20 -> 11h35 Coffee break
11h35 -> 12h20 — Hans van Ditmarsch (LORIA)
Titre:Dynamic epistemic logic for distributed computing - asynchrony and concurrency
We will present some recent work on asynchrony and concurrency in dynamic epistemic logics (DEL), building on foundations in distributed computing and temporal epistemic logics.
Asynchrony can be modelled by reasoning over histories of actions of different length. How to do this in DEL was proposed by [Dégremont, Löwe, Witzel: TARK 2011]. By equivalence relations on protocol-generated forests along different depths of trees, they can identify action histories of different length. More or less strongly related to DEL this was also considered for: gossip protocols [Apt, Grossi, vd Hoek, TARK 2015], logic puzzles [vD, van Eijck, Wu: KR 2010], and for the immediate snapshot algorithm in distributed computing [Goubault, Ledent, Rajsbaum: GandALF 2018]. We will present the last in some detail: Kripke models and action models can be represented as simplicial complexes. Dynamic epistemic logic can then be interpreted on such complexes.
From the perspective of dynamic epistemic logic, a further departure towards distributed computing and asynchrony is to distinguish the sending and receiving of messages, such as the making versus hearing of announcements. Recent proposals are [Knight, Maubert, Schwarzentruber; MSCS 2019] and [Balbiani, vD, Fernandez Gonzalez; ArXiV 2019] (SR 2017). From the latter we will present asynchronous announcement logic. Its axiomatization resembles that of public announcement logic, and the dynamic modalities can also be eliminated. Further research is on (what is known as) concurrent common knowledge.
Finally, how do we model concurrency in DEL? Both true concurrency and intersection concurrency are conceivable. We recall some older work in the area: [vD, vd Hoek, Kooi: AAMAS 2003] and [van Eijck, Sietsma, Wang: JANCL 2011]. The Muddy Children Problem is a joy forever: the action of three muddy children not stepping forward because none of them know whether they are muddy, is always modelled as the public announcement of a conjunction with three conjuncts. Should this not be a concurrent action with three components?
End: 12h30
Conference : soutenance HDR Benoit FAVRE : St Charles
15/11/2019 à 15h00
J'ai le plaisir de vous inviter à ma soutenance d'HDR, intitulée "Contextual natural language understanding", qui aura lieu à la salle des voutes à St-Charles le mardi 12 novembre à 15h.Le jury est composé de :
- Martine Adda-Decker, DR CNRS/LIMSI, Sorbonne Nouvelle Paris 3, rapporteure
- Thierry Artières PR, Aix-Marseille Université, examinateur
- Frédéric Béchet, PR, Aix-Marseille Université, examinateur
- Guillaume Gravier, CR CNRS/IRISA Rennes, rapporteur
- Patrick Gallinari, PR LIP6 Sorbonne Université, rapporteur
- Dilek Hakkani-Tür, Amazon San Francisco, examinatrice
Seminaire : Séminaire de l'équipe I&M : "Bridging the gap between in-vivo and ex-vivo brain dissection"
15/11/2019 à 10h00
Séminaire de l'équipe I&M qui aura lieu vendredi 15/11 au TPR1 salle G 02.12 entre 10h et 12h (campus Luminy) : Paolo Avesani, University of Trento.
Titre "Bridging the gap between in-vivo and ex-vivo brain dissection"
Résumé:
The anatomy of neuroanatomical brain connections can be characterized in-vivo at the individual level from recordings of diffusion MRI. After a first a step of diffusivity model reconstruction, and a subsequent step of fiber tracking we may obtain a representation of structural brain connectivity, namely a tractogram, as a collection of millions of streamlines, where each streamline is encoded as a polyline. The task of tract dissection from a tractogram, referred also as virtual dissection in contrast to ex-vivo dissection, is concerned with the identification of those streamlines that have a specific neuroanatomical meaning. On the other hand we may investigate the brain connectivity by dissecting ex-vivo human brain using the Klinger techniques. By sculpturing the brain tissue we may expose those fibers that characterize a specific neuroanatomical bundle. Taking advantage of photogrammetric techniques it is possible to reconstruct a 3D model and to enable a comparison with the 3D model acquired using magnetic resonance. Up to now the joint analysis of ex-vivo and in-vivo brain dissection is carried out by qualitative descriptions. In this presentation we present the preliminary results in the direction of combining brain data acquired ex-vivo with photogrammetric techniques, and those acquired in-vivo with magnetic resonance.Biographie du conférencier :
Paolo Avesani received the PhD degree from the University of Milan, Italy. He is a researcher at Bruno Kessler Foundation (FBK ) in Trento (Italy) , where he is leading the Neuroinformatics Laboratory (NILab) — a joint initiative of FBK and the Center for Mind/Brain Sciences (CIMeC), University of Trento. His current research interests include machine learning, functional neuroimaging analysis, computational methods for brain decoding and brain mapping.Seminaire : Séminaire MOVE : Nathan Lhote (University of Warsaw)
14/11/2019 à 10h30
Séminaire MOVE : Nathan Lhote (University of Warsaw) Jeudi 14 novembre, 10h30 Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy Titre : Some recent results on polyregular functions Résumé : Regular word functions are well-studied and correspond to several different formalisms: MSO-transductions, two-way transducers, one-way transducers with registers (SST), as well as several formalisms of regular expressions for transducitons. Polyregular functions were introduced last year in an article of Bojańczyk, where they are shown to be characterized by 4 different models of computation. The first one, which comes from [Milo, Suciu, Vianu '03], is an extension of two-way transducers with a bounded number of pebbles. Polyregular functions have polynomial size increase, which means in particular that they strictly subsume regular functions; however, they still retain some of the nice properties of regular functions, such as preserving regular languages by inverse image, and being closed under composition. In this talk we present polyregular functions, and two results that were obtained this year.Conference : G-MOD : journées du GRD IG-RV (Informatique Graphique et Réalité Virtuelle)
12/11/2019 à 09h00
L’équipe G-Mod organise en partenariat avec l’Institut des Sciences du Mouvement les journées du GRD IG-RV (Informatique Graphique et Réalité Virtuelle). Ces journées JFIGRV2019 se décomposent en : - une journée jeunes chercheurs le 12 novembre à Luminy (Polytech)- 3 jours de conférence les 13, 14 et 15 novembre au Palais des Congrès du Parc Chanot
Toutes les informations sont disponibles sur le site de la conférence : https://jfigrv2019.sciencesconf.org
Si tu penses que cette info doit être diffusée par mail, n’hésite pas
Seminaire : Séminaire MOVE : Denis Kuperberg (CNRS, LIP, ENS Lyon)
07/11/2019 à 10h30
Séminaire MOVE : Denis Kuperberg (CNRS, LIP, ENS Lyon) Jeudi 7 novembre, 10h30 Salle de réunion du bâtiment modulaire BP5 (en bas de l'ancienne BU), Luminy Titre : Circular proof systems for regular expressions Résumé : Cyclic proofs are a class of formal proof systems that allow some kind of circular reasoning. Unlike classical proofs, represented by finite trees with axioms as leaves, cyclic proofs are represented by trees containing infinite branches. We investigate the computational content of a cyclic proof system for Kleene algebra. If e,f are regular expressions, the sequent e -> f can be proved in the cyclic proof system if and only if L(e) is contained in L(f). Different proofs of the same sequent can be interpreted as different programs mapping each word of e to a witness that it is in f. We show that depending on the particular rules allowed in the system, the computational content of proofs matches different complexity classes. In particular, if the contraction rule is added, we obtain a rich class of languages, for which we exhibit an equivalent automaton model: Jumping Multihead automata. In presence of the cut rule, corresponding to composition of programs, we can define primitive recursive functions (without contraction) or functions from System T (with contraction). This is joint work with Laureline Pinault and Damien PousRencontre : LIS PhDay 2019, St Jérôme
31/10/2019 à 09h30
Le LIS PhDay 2019, rassemblement annuel des jeunes chercheurs du LIS (doctorants, ATER, postdocs), aura lieu jeudi 31 octobre 2019, salle de conférence du bâtiment Polytech/LIS sur le site St Jérôme à Marseille. Programme prévisionnel: 9h15: accueil 9h30 : 3-4 interventions scientifiques (20-25'/pers) 11h : pause 11h15 : 3-4 interventions scientifiques (20-25'/pers) 12h30 : buffet 14h : rencontre avec anciens 15h30 : activité détente, team-building 18h: apéro en ville Inscription en 30s (aidez-nous à ajuster les quantités!) : https://forms.gle/g8uU4SknutQJh2hD7Seminaire : Séminaire CaNa -- Quasériodes des mots biinfinis, Guilhem Gamard
29/10/2019 à 14h00
Un mot fini q est une quasipériode d’un mot infini w si et seulement si w est recouvert de copies de q, éventuellement chevauchantes. Si w admet au moins une quasipériode, on dit qu’il est quasipériodique. Cette notion est apparue dans les années 1990 dans un contexte d’algorithmique du texte, puis fut employée en combinatoire des mots, ainsi que dans l’étude des subshifts.Un article récent (2016) donne une technique générale permettant de déterminer l’ensemble des quasipériodes d’un mot infini donné. Cette technique permet par exemple de caractériser les quasipériodes des mots sturmiens. En outre, elle permet de démontrer que les mots sturmiens standard sont les mots apériodiques possédant “le plus de quasipériodes possibles”. La première partie de cet exposé présentera ces résultats.
Malheureusement, tous ces résultats ne portent que sur les mots infinis à droite ; dans le cas des mots biinfinis, la combinatoire du problème est considérablement plus compliquée. Le cas biinfini est cependant plus naturel pour la dynamique symbolique, car le shift d’un mot biinfini quasipériodique est encore quasipériodique (ce qui n’est pas vrai sur les mots infinis à droite). Dans la deuxième partie de cet exposé, nous verrons comment généraliser les résultats précédents au cas biinfini.
Seminaire : DALGO: Arnaud Labourel (LIS), vendredi 25 octobre à 10h30. Livraison collaborative avec des agents mobiles contraints en énergie.
25/10/2019 à 10h30
Titre : Livraison collaborative avec des agents mobiles contraints en énergie.Orateur: Arnaud Labourel
Lieu : salle de réunion du LIS, Luminy (Préfabriqué)
Résumé:
Dans cet exposé je vous parlerai du problème de livraison collaborative avec des agents mobiles. On considère un graphe pondéré (orienté ou non) dans lequel se trouve des agents mobiles initialement dispersés. L’objectif des agents est de transporter un colis d’un sommet source à un sommet destination. Chaque agent a un montant d'énergie limité lui permettant de parcourir une trajectoire de longueur au plus B. Les agents doivent donc collaborer car aucun n’a assez d’énergie pour transporter seul le colis de la source à la destination. Ce problème avait déjà été étudié mais nous ajoutons une contrainte supplémentaire qui est que les agents doivent utiliser uniquement un chemin prédéfini pour transporter le colis. Cette contrainte peut se justifier par des raisons de sécurité, en considérant qu'un seul chemin est sûr dans le réseau pour transporter le colis. Bien que cette contrainte réduise l’espace de recherche des solutions réalisables, le problème reste difficile à résoudre tout comme l’est le problème initial. Je vous montrerai des algorithmes d’approximation (pour le montant d’énergie B des agents) en temps polynomial pour les graphes orientés et non orientés, et vous donnerai une preuve de NP-dureté pour l’approximation dans le cas orienté.
Travail en collaboration avec Jérémie Chalopin, Shantanu Das, Yann Disser et Matúš Mihalák
Seminaire : Séminaire MoVe/LIRICA : Karoliina Lehtinen (Univ. Liverpool) - 24 octobre - Quasi-polynomial techniques for parity games and and other problems
24/10/2019 à 11h00
Parity games are central to the verification and synthesis of reactive systems: various model-checking, realisability and synthesis problems reduce to solving these games. Solving parity games -- that is, deciding which player has a winning strategy -- is one of the few problems known to be in both UP and co-UP yet not known to be in P. So far, the quest for a polynomial algorithm has lasted over 25 years. In 2017 a major breakthrough occurred: parity games are solvable in quasi-polynomial time. Since then, several seemingly very distinct quasi-polynomial algorithms have been published, and some of these ideas have been used to solve other automata-theoretic problems. In this talk, I will give an overview of these developments and the state-of-the art, with a slight automata-theoretic bias.Lieu : Amphithéâtre Herbrand (I2M, TPR2, 1er étage), Luminy
Séminaire joint MoVe/LIRICA/LDP (I2M)
Plus d'infos sur la page du séminaire MoVe : lien
Seminaire : Séminaire ACS : Gabriel Wainer (Carleton University)
21/10/2019 à 14h00
Lieu : Sy. Jérôme, salle des commissions. Titre: Discrete Event Modeling and Simulation Methodologies : Past, Present and Future. Resumé : Modeling and Simulation methods have been used to better analyze the behavior of complex physical systems and it is now common to use simulation as a part of the scientific and technological discovery process. M&S advanced thanks to the improvements in computer technology, which, in many cases, resulted in the development of simulation software using ad-hoc techniques. Formal M&S appeared in order to try to improve the development task of very complex simulation systems. Some of these techniques proved to be successful in providing a sound base for the development of discrete-event simulation models, improving the ease of model definition and enhancing the application development tasks; reducing costs and favoring reuse. The DEVS formalism is one of these techniques, which proved to be successful in providing means for modeling while reducing development complexity and costs. DEVS model development is based on a sound theoretical framework. The independence of M&S tasks made possible to run DEVS models on different environments (personal computers, parallel computers, real-time equipment, and distributed simulators) and middleware. We will present a historical perspective of discrete-event M&S methodologies, showing different modeling techniques. We will introduce DEVS origins and general ideas, and compare it with some of these techniques. We will then show the current status of DEVS M&S, and we will discuss a technological perspective to solve current M&S problems (including real-time simulation, interoperability and model-centered development techniques). We will show some examples of the current use of DEVS, including applications in different fields. We will finally show current open topics in the area, which include advanced methods for centralized, parallel or distributed simulation, the need of real-time modeling techniques, and our view in these fields.Seminaire : DALGO: Peter Niebert et Cédric Berenger (LIS), vendredi 27 septembre à 10h30. Ce que vos parents ont dit de ne pas faire dans un protocole sans fil
27/09/2019 à 10h30
Titre : Ce que vos parents ont dit de ne pas faire dans un protocole sans filOrateurs: Cédric Berenger et Peter Niebert
Lieu : salle de réunion du LIS, Luminy (Préfabriqué)
Résumé: Nous présentons deux travaux en cours dans le domaine des protocoles sans fil qui ont en commun d’exploiter des transgressions de l’usage habituel de la couche physique. Pour comprendre ces travaux, nous introduisons d’abord le côté physique de la couche MAC de Bluetooth Low Energy, puis nous montrons, démonstration à l’appui, comment certains détournements de cette couche physique ouvrent des possibilités inattendues dans la conception de protocoles sans fil.
Seminaire : 3ème Demi-journée Pole Calcul - Algorithmique et Structure Discrete - 26 septembre
26/09/2019 à 09h30
Dans le cadre du deuxième cycle des demi-journées du Pole Calcul du LIS, la prochaine sera autour du thème “Algorithmique et Structure Discrete”, organisée le jour 26 Septembre 9h30 à 12h30 dans la salle des séminaires au 3ème étage du FRUMAM de Saint Charles. Les deux intervenants confirmés sont Guilherme Dias da Fonseca (MCF, LIS) et Yan Gerard (MCF, UCA).Troisième demi-journée (“Algorithmique et Structure Discrete”) 26 Septembre
(45min each + 10 mins questions + 15 min coffe break)
9h30 -> 10h15 —PhD Student (TBC), LIS
Titre: --
--
10h25 -> 11h10 — Guilherme Dias da Fonseca (MCF, LIS)
Titre: Fast Algorithms for Unit Disk Graphs
Unit-disk graphs are graphs whose $n$ vertices correspond to
unit disks in the plane and whose $m$ edges correspond to pairs of
intersecting disks. \emph{Graph-based} algorithms receive as input
solely the adjacency representation of the graph while
geometric algorithms receive the coordinates of the disks. In
this talk, we consider approximation algorithms to two classic hard
optimization problems: maximum independent set and minimum dominating
set. We are particularly interested in algorithms whose running times
are close to linear in the input size, i.e. close to $O(n+m)$ for
graph-based algorithms and close to $O(n)$ for geometric algorithms.
We will discuss four different approaches to obtain such algorithms:
greedy, local search, strip decomposition, and shifting coresets,
comparing their performance for different problems and graph classes.
This work is based on multiple papers co-written by the author with
Celina M. H. de Figueiredo, Vinicius G. Pereira de Sá, Raphael
Machado, Gautam K. Das, and Ramesh K. Jallu.
11h20 -> 11h35 Coffee break
11h35 -> 12h20 — Yan Gerard (PR, UCA)
Titre: two open problems of Digital Geometry with convex lattice sets-
A lattice set of $Z^d$ is digital convex if its real convex hull does not contain any other integer point than the ones of S.
Problem 1: recognition of digital polyhedra.
A n-digital polyhedron is the intersection of the lattice $Z^d$ with a polyhedron of $R^d$ with at most $n$ faces. Given $n$ and a convex lattice set $S$, we want to determine whether $S$ is a $n$-digital polyhedron. In dimension $d=2$, with $n=3$, the question is to determine whether there exists a triangle $T$ whose intersection with the lattice is $S$. Whatever the value of $n$, it is a very natural question related to polyhedral separability but it is still undetermined whether it is decidable in the cases where $d>3$ and $S$ is hollow (hollow means that the interior of its convex hull does not contain any integer point).
Problem 2: Discrete Tomography
We consider the problem of reconstruction of convex lattice sets (or HV-convex polyominoes) from their horizontal and vertical X-rays or projections. In other words, we know the number of points of a convex lattice set $S$ on each row and column, and we want to reconver $S$. It's not known whether it can be done in polynomial time. The usual approach to tackle the problem is based on some combinatorial objects called the switching components. We present some recent results abour their structures.
End: 12h30
Conference : Pierre Zweigenbaum - Extraction d'information dans le domaine biomédical à base de corpus et de connaissances
23/09/2019 à 14h00
Nous avons le plaisir d'accueillir Pierre Zweigenbaum (LIMSI - https://perso.limsi.fr/pz/), un des plus grands experts du TAL biomédical en France, pour un séminaire conjoint QARMA+TALEP le lundi 23/09/2019 à 14h à StCharles, dans la salle de séminaires de la FRUMAM, 2eme étage. Le titre et le résumé sont ci-dessous. Extraction d'information dans le domaine biomédical à base de corpus et de connaissances Résumé: Le séminaire sera composé de deux parties. Dans la première partie, je ferai un survol de plusieurs de nos travaux récents en TAL biomédical : extraction de symptômes et traitements dans des forums de santé, normalisation d'informations dans les certificats de décès, TAL pour la formation des médecins. Dans la deuxième partie, je me concentrerai sur un travail récent (thèse d'A Ferré) autour du plongement d'ontologie pour le liage référentiel. La tâche de normalisation d'entité consiste en la mise en correspondance automatique de mentions d'entités dans des textes avec les concepts d'un référentiel, typiquement une ontologie. Pour réaliser cette tâche en alliant corpus et connaissances a priori, nous proposons une nouvelle approche par alignement de deux types de représentations vectorielles d'entités capturant une partie de leur sens : les plongements lexicaux pour les mentions textuelles et des « plongements ontologiques » pour les concepts, conçus spécifiquement pour ce travail. L'alignement entre les deux se fait par apprentissage supervisé. Les méthodes développées ont été évaluées avec un jeu de données de référence du domaine biologique et elles représentent aujourd'hui l'état de l'art pour ce jeu de données.Seminaire : DALGO: Fabien Dufoulon (LRI), vendredi 13 septembre à 10h30
13/09/2019 à 10h30
Titre: Overcoming Interference in the Beeping Model: Deterministic Optimal Leader Election Orateur: Fabien Dufoulon (LRI, Paris) Lieu : salle de réunion du LIS, Luminy (Préfabriqué) Résumé: Small inexpensive inter-communicating electronic devices have become widely available. Although the individual device has severely limited capabilities (e.g., basic communication, constant-size memory or limited mobility), multitudes of such weak devices communicating together are able to form low-cost, easily deployable, yet highly performant networks. Such distributed systems present significant challenges however when it comes to the design of efficient, scalable and simple algorithms. In this presentation, we will focus on such systems, composed of devices with severely limited communication capabilities - using only simple bursts of energy. These distributed systems may be modeled using the beeping model, in which nodes communicate by beeping or listening to their neighbors (according to some undirected communication graph). This model was recently introduced (Cornejo and Kuhn, 2010), raising several question about the impact of beeping communication on fundamental problems, such as leader election, vertex coloring or multi-broadcast. Focusing on the leader election problem, we present the first deterministic optimal leader election beeping algorithm, which requires nodes to have unique identifiers. We also present a randomized version of this solution, working with anonymous nodes. This randomized solution is the first optimal randomized leader election beeping algorithm.Seminaire : Séminaire de Théorie du Contrôle de Toulon. Thibault Maillot : Utilisation d'un modèle agronomique et d'algorithme d'optimisation afin de trouver des systèmes de cultures qui permettent d'avoir des compromis entre des indicateurs de biodiversité et de
18/07/2019 à 15h00
Seminaire : Séminaire CaNa : Jeudi 11 Juillet : Nathanaël Eon : Invariance de jauge dans les automates cellulaires
11/07/2019 à 14h00
L'invariance de jauge est une symétrie fondamentale en physique, permettant la dérivation des quatre interactions fondamentales (électromagnétique, faible, forte, gravitationnelle). D'autre part, les automates cellulaires sont largement reconnus comme un modèle de calcul naturel utile à la modélisation de phénomènes physiques. Cet exposé à pour but de montrer comment ces deux théories peuvent être réunies et les perspectives que l'on peut en tirer. L'exposé présentera les résultats obtenus pendant mon alternance ainsi que mon stage de M2. Gauge-invariance is an essential symmetry in Physics as it allows for the derivation of the four fundamental interactions (namely electromagnetic, weak, strong and gravitation). From a different perspective, cellular automata are a model of natural calculus largely known for its capacity to model physical phenomena. This talks aims at uniting those two theories and see what perspectives comes from such unification. The results presented comes from a research project which encapsulate my M2 internship.Seminaire : Séminaire CaNa : Mardi 9 Juillet : Enrico Formenti : Computational complexity of finite asynchronous cellular automata
09/07/2019 à 14h00
Cellular Automata (CA) are a well-established bio-inspired model of computation that has been successfully applied in several domains. In the recent years the importance of modelling real systems more accurately has sparkled a new interest in the study of asynchronous CA (ACA). When using an ACA for modelling real systems, it is important to determine the fidelity of the model, in particular with regards to the existence (or absence) of certain dynamical behaviors. This paper is concerned with two big classes of problems: reachability and preimage existence. For each class, both an existential and a universal version are considered. The following results are proved. Reachability is PSPACE-complete, its resource bounded version is NP-complete (existential form) or coNP-complete (universal form). The preimage problem is dimension sensitive in the sense that it is NL-complete (both existential and universal form) for one-dimensional ACA while it is NP-complete (existential version) or PI^P_2-complete (universal version) for higher dimension. (article/pii/S0304397515011421)Seminaire : Séminaire CaNa : Alan Gardin : Etude d'un exemple de dynamique causale de graphe quantique
02/07/2019 à 14h00
Titre: Etude d'un exemple de dynamique causale de graphe quantique Abstract: La présentation concerne l'étude d'une dynamique causale de graphe quantique. Il existe des résultats théoriques sur le sujet, que j'espère éclairer en présentant un exemple d'une telle dynamique. J'expliquerai notamment comment ce modèle a été construit, et quels ont été les problèmes rencontrés. Une fois cet exemple défini, je m'intéresserai aux applications potentielles de ce modèle, et plus particulièrement aux capacités de calcul. Enfin, j'aborde l'étude théorique de ce modèle d'un point de vue mathématique. Cette approche permettra éventuellement à terme de déduire certaines propriétés utiles à l'étude des capacités de calculs du modèle. Lieu : salle de réunion de bâtiment modulaire, à LuminySeminaire : Séminaire de Théorie du Contrôle de Toulon. Lucas Brivadis : Observateurs de Luenberger pour les systèmes linéaires en dimension infinie
26/06/2019 à 14h00
Dans cette présentation, nous nous intéressons aux observateurs de type Luenberger dans le contexte des systèmes linéaires en dimension infinie. Dans [1], les auteurs montrent, sous une hypothèse d’observabilité du sytème, que l’erreur entre l’état du système et son observateur converge faiblement vers zéro. Nous cherchons à généraliser ce résultat, puis à l’adapter au contexte des observateurs itératifs à horizon fini. Toutefois, [2] propose dans ce même contexte un cadre dans lequel la convergence forte de l’erreur est satisfaite. Nous montrons comment étendre ce résultat aux observateurs asymptotiques usuels et le comparons aux résultats de [1]. Enfin, nous illustrons nos propos par une application au design d’un observateur pour un procédé de cristallisation en batch basé sur la technologie FBRM. [1] F. Celle et al. “Synthesis of nonlinear observers: A harmonic-analysis approach”. In: Mathematical systems theory 22.1 (Dec. 1989), pp. 291–322. [2] G. Haine, “Recovering the observable part of the initial data of an infinite-dimensional linear system with skew-adjoint generator” In: Math. Control Signals Syst. (2014) 26: 435.WorkShop : Workshop on Machine Learning and Quantum Computation
26/06/2019 à 14h00
Université d'Aix-Marseille, LIS, Marseille, France http://pageperso.lif.univ-mrs.fr/~hachem.kadri/workshopMLQC/index.htmlWorkshop Date: June 26, 2019
Venue: The workshop will be hosted in Marseille at FRUMAM.
Registration: free
The goal of this workshop is to bring together researchers interested in all aspects of quantum computation models and their use in machine learning. It promotes the cross-fertilizing exchange of ideas and experiences among researchers from the communities of machine learning and quantum computing interested in the foundations and applications of quantum computation models and machine learning.
Confirmed Invited Speakers- Stéphane Ayache, LIS, TBC
- Luc Giffon, LIS, Deep Networks with Adaptive Nyström Approximation
- Benoît Grémaud, CPT, Quantum tensor networks: from condensed matter to machine learning
- Anupam Prakash, IRIF, Quantum Support Vector Machines
- Giuseppe Di Molfetta - LIS, Aix-Marseille University
- Hachem Kadri - LIS, Aix-Marseille University
Seminaire : Séminaire : ligne de force "Gestion et fouille de données pour l’extraction de connaissances" du pôle SD.
17/06/2019 à 09h30
Lundi 17 juin, nous aurons le plaisir d'accueillir Adbelkader Hameurlain, professeur à l'IRIT (Toulouse) et responsable de l'équipe Pyramid (http://www.irit.fr/-Equipe-PYRAMIDE-). Ce séminaire s'inscrit dans la ligne de force Gestion et fouille de données pour l’extraction de connaissances du pôle SD. Le séminaire se déroulera dans les locaux de la FRUMAM, deuxième étage, salle des séminaires de 9h30 à 12h00. 09h30 : Accueil avec café gourmand 10h00 : Séminaire suivi de questions et de discussions Title: Data Management in the Cloud: Evolution or Crossroad? Abstract: In the landscape of database management systems, data analysis systems (OLAP) and transaction processing systems (OLTP) are separately managed. The reasons for this dichotomy are that both systems have very different functionalities, characteristics and requirements. My talk will focus on the first class of OLAP systems. The purpose of this talk is twofold: (i) to provide a synthetic state of the art concerning (large-scale) data management systems, and (ii) how can the evolution of these systems help for big data applications. In this perspective, data management based on parallel and cloud systems are overviewed and compared by relying on fundamental criterion such as Software Requirements (Data Independence, Software Reuse), High Performance, Data Availability, Fault Tolerance, Scalability and Elasticity. With respect to the state of the art, proposed systems, and qualitative and quantitative comparative studies between Parallel DBMS (PDBMS) and Big Data Management Systems (BDMS), we try to learn some lessons and point out some open issues that should be tackled to ensure the viability of the next generation of large-scale data management systems for big data applications. Key Words: Big Data Management, Data Partitioning, Data Integration, Parallel Database Systems, Cloud Data Management Systems, Query Processing and Optimization, High Performance, Scalability, Elasticity, Hadoop MapReduce, Spark, Multistore Systems.Seminaire : 2ème Demi-journée Pole Calcul - Topologie et Géométrie du Calcul - 6 juin
06/06/2019 à 09h30
Dans le cadre du deuxième cycle des demi-journées (le détail ici) du Pole Calcul du LIS, la prochaine sera autour du thème “Géométrie et topologie du calcul”, organisée le jour 6 Juin 9h30 à 12h30 dans l’Amphi Massiani de Saint Charles. Les trois intervenants confirmés sont Alexandra Bac (LIS), Emmanuel Godard (LIS) et Clement Maria (INRIA, http://www-sop.inria.fr/members/Clement.Maria/)Deuxième demi-journée (Géométrie et topologie du calcul) 6 Juin
(45min each + 10 mins questions + 15 min coffe break)
9h30 -> 10h15 —Emmanuel Godard, LIS
Titre: Back to the Coordinated Attack Problem
We consider the well known Coordinated Attack Problem, where two gener- als have to decide on a common attack, when their messengers can be captured by the enemy. Informally, this problem represents the difficulties to agree in the present of communication faults. We consider here only omission faults (loss of message), but contrary to previous studies, we do not to restrict the way mes- sages can be lost, i.e. we make no specific assumption, we use no specific failure metric. In the large subclass of message adversaries where the double simulta- neous omission can never happen, we characterize which ones are obstructions for the Coordinated Attack Problem. We give two proofs of this result. One is combinatorial and uses the classical bivalency technique for the necessary con- dition. The second is topological and uses simplicial complexes to prove the necessary condition. We also present two different Consensus algorithms that are combinatorial (resp. topological) in essence. Finally, we analyze the two proofs and illustrate the relationship between the combinatorial approach and the topological approach in the very general case of message adversaries. We show that the topological characterization gives a clearer explanation of why some message adversaries are obstructions or not. This result is a convincing illustration of the power of topological tools for distributed computability.
Joint work with Eloi Perdereau
10h25 -> 11h10 — Alexandra Bac (MCF), LIS
Titre : Analyse et reconstruction de modèles 3D : approches géométriques et topologiques
Avec la généralisation de l’outil informatique dans tous les domaines de la société civile, la modélisaton géométrique est devenue une plaque tournante incontournable. Pour expliquer son essor, commençons peut-être par une tentative de définition :
"La modélisation géométrique, à la croisée des Mathématiques et de l’Informatique Graphique, a pour but de construire et analyser des modèles virtuels d’objets réels ou virtuels."
Différents facteurs ont contribué à élargir le statut de la modélisation géométrique pour le faire passer de discipline relativement académique à celui d’outil applicatif indispensable :
- d’une part, l’essor des modèles virtuels comme outils (la conception assistée par ordinateur est devenue un passage obligé dans tous les domaines de l’industrie et du design),
- d’autre part, celui des méthodes de télédétection (que ce soit dans le médical, physique, chimie, génétique urbanisme, archéologie, géologie, aéronautique, étude de l’univers, de la terre, du sous-sol, des environnements naturels ou marins ...),
- enfin avec la confirmation de la loi de Moore, les capacités de traitement des ordinateurs ont atteint une développement suffisant pour permettre l’application d’algorithmes jusque-là inaccessibles sur les masses de données générées par les moyens de télédétection modernes.
La topologie, quant à elle, étudiant “les propriétés invariantes sous l’effet de transformations biunivoques continues” (Riemann), est longtemps restée un domaine de recherche purement mathématique. Cependant, avec le développement de l’informatique et de la recherche informatique, cette frontière a rapidement fissuré, ouvrant le pas à l’étude algorithmique de la topologie des objets discrets. La topologie algébrique, branche de la topologie générale, vit ainsi naître son pendant numérique : la topologie algébrique algorithmique.
La présentation abordera deux grandes pôles contiguës et complémentaires :
1. la géométrie (principalement la géométrie des surfaces)
2. la topologie algorithmique (et plus particulièrement l’homologie algorithmique)
11h20 -> 11h35 Coffee break
11h35 -> 12h20 — Clement Maria, INRIA, http://www-sop.inria.fr/members/Clement.Maria/
Titre: Faster computation on simple topologies-
Resumé: The complexity of solving topological problems on surfaces often depends on the topology of the input surface. For example, deciding whether a graph can be embedded on a surface is NP-hard in general, but becomes only linear time on the size of the graph if the genus of the surface is considered constant.
In this talk, we focus on a powerful topological invariant of 3-manifolds satisfying a similar property. Specifically, we introduce a fixed parameter tractable algorithm for computing the Turaev-Viro invariant at the fourth root of unity, using the dimension of the first homology group of the manifold as parameter. This invariant is #P-hard to compute in general. This is joint work with Jonathan Spreer.
End: 12h30
Seminaire : Séminaire CaNa : Sabrina Ouazzani : Machines de Turing à temps infini: des fondements aux applications
04/06/2019 à 14h00
Titre: Machines de Turing à temps infini: des fondements aux applications Résumé: Dans cet exposé je vous présenterai les fondements des machines de Turing à temps infini, en particulier comment calculer avec et quelques unes de leurs particularités issues de mes travaux de recherche, mais j’en présenterai aussi de nouvelles applications, notamment en analyse, sur lesquelles je travaille actuellement avec Olivier Bournez. En particulier, quels liens ces machines entretiennent-elles avec les équations différentielles ? Je conclurai en introduisant quelques questions d’ouverture.Seminaire : Séminaire du pôle SD autour de la ligne de force "Multimodalité et Interaction"
03/06/2019 à 10h00
Le prochain séminaire du pôle SD autour de la ligne de force "Multimodalité et Interaction" aura lieu le lundi 3 juin à St Charles à l'espace Pouillon (à côté de la bibliothèque sur le campus de St Charles), de 10h à 13h00. Nous vous proposons une présentation invitée de Julia Peyre intitulée "Learning to detect visual relations in images" puis une série de présentations des travaux des équipes sur cette ligne de force. Au plaisir de vous voir le 3 juin matin, Magalie et Alexis.Conference : Séminaire DALGO: Dariusz Dereniowski (Gdansk University of Technology, Pologne)
29/05/2019 à 10h30
Titre : A Framework for Searching in Graphs in the Presence of Errors Lieu: salle de réunion du LIS (préfabriqué) Résumé: We consider a problem of searching for an unknown target vertex t in a (possibly edge-weighted) graph. Each vertex-query points to a vertex v and the response either admits that v is the target or provides any neighbor s of v that lies on a shortest path from v to t. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh- Zadeh et al. [STOC 2016]. In the latter, the authors provide algorithms for the error-less case and for the independent noise model (where each query independently receives an erroneous answer with known probability p < 1/2 and a correct one with probability 1 − p). We study this problem both with adversarial errors and independent noise models. First, we show an algorithm that needs at most (log n)/(1-H(r)) queries in case of adversarial errors, where the adversary is bounded with its rate of errors by a known constant r < 1/2. Our algorithm is in fact a simplification of previous work, and our refinement lies in invoking an amortization argument. We then show that our algorithm coupled with a Chernoff bound argument leads to a simpler algorithm for the independent noise model and has a query complexity that is both simpler and asymptotically better than the one of Emamjomeh-Zadeh et al. [STOC 2016]. Our approach has a wide range of applications. First, it improves and simplifies the Robust Interactive Learning framework proposed by Emamjomeh-Zadeh and Kempe [NIPS 2017]. Secondly, performing analogous analysis for edge-queries (where a query to an edge e returns its endpoint that is closer to the target) we actually recover (as a special case) a noisy binary search algorithm that is asymptotically optimal, matching the complexity of Feige et al. [SIAM J. Comput. 1994]. Thirdly, we improve and simplify upon an algorithm for searching of unbounded domains due to Aslam and Dhagat [STOC 1991]. (Joint work with S. Tiegel, P. Uznanski and D. Wolleb-Graf)Seminaire : Séminaire Unsupervised speech representation learning using WaveNet autoencoders : Jan Chorowski
28/05/2019 à 14h00
Jan Chorowski (University of Wrocław) Title: Unsupervised speech representation learning using WaveNet autoencoders Abstract: Learning representations of data in an unsupervised way is still an open problem of machine learning. We consider representations of speech learned using autoencoders equiped with WaveNet decoders. In this way, the encoder only needs to provide the little information needed to supplement all that can be inferred by the autoregressive decoder. This allows learning a representation able to capture high level semantic content from the signal, e.g. phoneme identities, while being invariant to confounding low level details in the signal such as the underlying pitch contour or background noise. I will show how the design choices of the autoencoder, such as the bottleneck kind its hyperparameters impact the induced latent representation. I will also show applications to unsupervised acoustic unit discovery on the ZeroSpeech task. Bio: Jan Chorowski is an Associate Professor at Faculty of Mathematics and Computer Science at the University of Wrocław. He received his M.Sc. degree in electrical engineering from the Wrocław University of Technology, Poland and EE PhD from the University of Louisville, Kentucky in 2012. He has worked with several research teams, including Google Brain, Microsoft Researchand Yoshua Bengio's lab at the University of Montreal. His research interests are applications of neural networks to problems which are intuitive and easy for humans and difficult for machines, such as speech and natural language processing.Seminaire : Séminaire Analyse et Contrôle des Systèmes : Gabriel Abba
23/05/2019 à 14h00
Titre: De la commande des robots bipèdes à celle des humanoïdes Résumé: Le but de ce séminaire est de présenter la conception et la commande de robots bipèdes. De l'analyse des modèles de ces robots et de celle de la marche, on peut déduire une commande hybride non linéaire stabilisant la marche. A partir du cas le plus simple d'un robot plan au cas des bipèdes 3D, on arrive progressivement à déterminer les conditions nécessaires pour élaborer la commande d'un robot humanoïde ainsi que de résumer les principales caractéristiques de ces robots.Seminaire : Séminaire CaNa : 23 Mai, Sara Riva
23/05/2019 à 14h00
Title: Solving Equations on Discrete Dynamical Systems Abstract: Boolean automata networks, genetic regulation networks, and metabolic networks are just a few examples of biological modeling by discrete dynamical systems (DDS). A major issue in modeling is the verification of the model against the experimental data or inducing the model under uncertainties in the data. Equipping finite discrete dynamical systems with an algebraic structure of semiring provides a suitable context for hypothesis verification on the dynamics of DDS. Indeed, hypothesis on the systems can be translated into polynomial equations over DDS. Solutions to these equations provide the validation to the initial hypothesis. Unfortunately, finding solutions to general equations over DDS is undecidable. However, many tractable cases have been highlighted. In this article, we want to push the envelop further by proposing a practical approach for such cases. We demonstrate that for many tractable equations all goes down to a "simpler'' equation. However for us, the problem is not to decide if the simple equation has a solution, but to enumerate all the solutions in order to provide an insight on the set of solutions of the original, undecidable, equations. We evaluate experimentally our approach and show that it has good scalability property.Conference : Journée LIS-LPL-ILCB - "Corpus et Systèmes de dialogues" - 22 mai - LPL, Aix
22/05/2019 à 10h00
Le LPL, le LIS et l'ILCB organisent une journée sur la question du dialogue et des systèmes de dialogues. Cette rencontre bénéficie de la présence parmi nous de Pierre Lison (Norwegian Computing Center) dans le cadre d'un PHC Aurora ainsi que de la visite de Lina Maria Rojas Barahona (Orange Labs). Programme - 10:00 - 11:00 : Modélisation du dialogue: contrôle du dialogue et corpus multilingues (Pierre Lison) -- Pause Café -- - 11:30 - 12:30 : A glance through Conversational agents (Lina Maria Rojas Barahona) -- Repas -- - 14:00 - 15:00 : Réunion de travail autour des systèmes de dialogues et des corpus conversationnels La journée se déroulera au LPL à Aix en Provence.Seminaire : Séminaire CaNa : 21 Mai, Filippo Miatto
21/05/2019 à 14h00
Title : Designing devices with Variational Quantum Circuits Abstract : The design of realistic quantum devices can be extremely challenging, due to the complexity of quantum interactions or to the scarcity of analytical methods in certain areas, such as non-gaussian optical interactions. My approach is to start from a network of random quantum interactions and then optimize their parameters until we obtain the desired device. This is possible with a Variational Quantum Circuit (VQC), which allows for gradient descent methods as the optimization workhorse. The advantage of this method is that the raw VQC can be composed of realistic devices and designed for full generality, which means that a) a solution consists in the explicit blueprint with all the correct parts, their connectivity and their parameters all sorted out and b) it can be applied to a variety of domains, not just quantum optical devices. I apply this method to the design of a realistic one-way quantum repeater, which includes non-gaussian quantum optical interactions and is therefore a very difficult problem to solve without clever numerical methods. A preliminary result shows that it is in principle possible to have a repeater interaction with at most a few hundred elementary optical elements, which is an extremely promising result. Our current goal is to combine our method with Reinforcement Learning techniques to design better and better raw VQCs that can achieve the same performance with fewer elements and ultimately lead to the simplest and cheapest versions of the devices that we look for.Seminaire : Séminaire CaNa : 14 Mai, 14h : Dominic Horsman
14/05/2019 à 14h00
Title: A new logic for quantum computing Abstract: In this talk I will give an introduction to the use of the ZX calculus of observables as a new language in which to frame quantum computing. In particular, I will focus on how it acts as a high-level design and compilation language for surface codes with lattice surgery. ZX calculus diagrams allow purely diagrammatic equational reasoning, and I will show how they are especially suited to representing the structures of surface codes. Looking particularly at the operations of lattice surgery, I show how the generators of the calculus form a direct model for splitting and merging operations. This has important implications for how we think about quantum information processing, and I will discuss a few such issues here.Seminaire : Séminaire CaNa : 6 Mai, 14h : Eurico Ruivo
06/05/2019 à 13h30
Title: Inference and of elementary cellular automata limit-graphs Abstract: Cellular automata are locally defined dynamical systems which are discrete in space, time and in the state variables, and capable of presenting arbitrarily complex global emergent behaviour. One core question in the study of cellular automata refers to their limit behaviour, that is, to the global dynamical features in a infinite time evolution. For finite time evolutions, one-dimensional cellular automata present dynamics which can be described by regular languages and, therefore, by finite automata. Also, there are growth patterns in the evolution of such finite automata for some cellular automata rules. In this work we present the formalisation of an automatic method to compute such structures. Based on this, the rules of the elementary cellular automata rule space were classified according to the existence of a growth pattern in their finite automata and a method to infer the limit graph of some elementary cellular automata rules by analysing the regular expressions describing their behaviour in finite-time is presented.Seminaire : Séminaire CaNa : Silvère Gangloff: The search for a complexity notion for organised dynamical systems
30/04/2019 à 14h00
Le séminaire aura lieu à Luminy, dans la salle de réunion du bâtiment modulaire. Résumé : The neuroscientists G. Tononi, O.Sporns and G.M. Edelman proposed in 1994 a notion of complexity, that they called neural complexity, which aims at measuring the balance in a system between independance or specialisation of its parts and their integration into the whole that have organised systems such as the brain. This work has attracted recently the attention of mathematicians: in 2009, J. Buzzi and L. Zambotti defined a class of functionals called intricacies, which includes the particular case of neural complexity, and studied the maximisers of these functionals. This notion of intricacy was studied by K. Petersen and B. Wilson (2016) in the frame of symbolic dynamics, and computed a formula for some intricacy for very elementary one-dimensional subshifts of finite type. In this talk, I will expose the basic material to understand this problem and make an overview of the literature. In the end, I will try to expose some directions for research on this subject.Seminaire : DALGO: Shantanu Das (LIS), vendredi 26 avril à 10h30
26/04/2019 à 10h30
Title: Patrolling on Dynamic Ring Networks Abstract: We study the problem of patrolling the nodes of a network collaboratively by a team of mobile agents, such that each node of the network is visited by at least one agent once in every I(n) time units, with the objective of minimizing the idle time I(n). While patrolling has been studied previously for static networks, we investigate the problem on dynamic networks with a fixed set of nodes, but dynamic edges. In particular, we consider 1-interval-connected ring networks and provide various patrolling algorithms for such networks, for k = 2 or k > 2 agents. We also show almost matching lower bounds that hold even for the best starting configurations. Thus, our algorithms achieve close to optimal idle time. Further, we show a clear separation in terms of idle time, for agents that have prior knowledge of the dynamic networks compared to agents that do not have such knowledge. This paper provides the first known results for collaborative patrolling on dynamic graphs. (Note: Joint work with Giuseppe. A. Diluna and Leszek A. Gasieniec.) Salle de réunion du LIF, Luminy (Préfabriqué)Seminaire : Séminaire Analyse et Contrôle des Systèmes
25/04/2019 à 14h00
Séminaire de Angelo Alessandri (DIME, Università di Genova) (Toulon)Seminaire : Séminaire CaNa : 02/04, 15h : Pedro Balbi de Oliveira
02/04/2019 à 15h00
Le séminaire de Pedro Balbi de Oliveira se déroulera le 2 avril 2019 en salle de réunion du BP5 à luminy.
Titre : "Could density determination be solved with one-dimensional binary cellular automata with asynchronous update?"
Abstract: This title reflects the question that will start to be addressed during my visit to LIS. In the talk I will discuss the background about it, and give some idea about how the problem can be tackled. In its original formulation, density determination refers to the problem of deciding, by means of a one-dimensional cellular automaton rule, which is the most frequent bit in a cyclic binary configuration. This is one of the most widely studied benchmark decision problems in the cellular automata literature. In spite of various positive and negative results already known on the problem, in its various formulations, the possibility of solving it with a rule being updated in a deterministic asynchronous fashion is still open.
Seminaire : Séminaire Analyse et Contrôle des Systèmes
28/03/2019 à 14h00
Séminaire de Hassan Hammouri (LAGEP, Lyon) St. JérômeSeminaire : Séminaire Analyse et Contrôle des Systèmes
21/03/2019 à 14h00
Séminaire de Frédéric Mazenc (L2S)Seminaire : [1ère demi-journée Pole Calcul LIS] “Logique et Méthodes formels”
21/03/2019 à 09h30
Dans le cadre du deuxième cycle des demi-journées du Pole Calcul du LIS, la prochaine sera autour du thème “Logique et Méthodes formels”, organisée le jour *21 Mars 9h30 à 12h30 (Luminy) dans l’Amphi 12 de Luminy.
Les demi-journées seront aussi enregistrés et on les rendra publique les vidéos sur une page dédiée ou sur une chaine youtube (lien à venir).
Les trois intervenants confirmés sont Damien Busatto-Gaston (LIS), Belaid Benhamou (LIS), Jean-Francois Raskin (ULB)
Première demi-journée (Logique et Méthodes formelles) 21 Mars
(45min each + 10 mins questions + 15 min coffe break)
9h30 -> 10h15 — Damien Busatto-Gaston (PhD) , LIS
Titre : Synthesizing robust controllers for Büchi conditions in timed systems.
Abstract :
We solve the robust controller synthesis problem in timed automata with Büchi acceptance conditions. The goal of the controller is to play according to an accepting lasso of the automaton, while resisting to timing perturbations chosen by a competing environment. The talk will introduce classical notions for studying timed automata (regions, zones, constraint graphs) and explain how these can be extended to compute strategies that are resilient to arbitrarily small perturbations. We will also introduce a way to compute the largest perturbation allowed by a given controller. Our techniques are illustrated by the regulation of a train network.
10h25 -> 11h10 — Belaid Benhamou (MCF), LIS
Titre : Programmation logique au sens ASP (Answer Set Programming) : une nouvelle sémantique capturant et étendant celle des modèles stables.
Abstract :
Plusieurs travaux ont été faits pour définir des sémantiques pour les programmes logiques normaux. La plupart de ces sémantiques sont en fait des sémantiques de points fixes. L’idée principale est le calcul de modèles canoniques du programme logique considéré, appelés modèles stables (Gelfond et al. 1988). Dans cette exposé, nous décrivons une nouvelle sémantique pour les programmes logiques normaux. Cette dernière est basée sur une notion d’extensions de formules propositionnelles classiques. Un programme logique est alors codé par un ensemble de clauses de Horn propositionnelles. On prouve que chaque formule consistante (ou programme logique) admet au moins une extension et que, pour chaque modèle stable d’un programme logique, il existe une extension de son codage logique qui l’implique. Certaines extensions (extra-extensions) ne correspondent pas à des modèles stables du programme logique, mais sont intéressantes car elles représentent ici, une extension pour la sémantique des modèles stables. Nous donnons une condition discriminante simple qui permet de reconnaître les extensions « normales » et les distinguer des extra-extensions. Basé sur cette sémantique, nous proposons une nouvelle méthode de recherche de modèles stables pour les programmes logiques. Elle a l'avantage d'utiliser un ensemble de clauses de Horn et travaille à espace constant. Elle évite ainsi, la lourdeur induite par la gestion des boucles, dont souffrent la plupart des solveurs ASP utilisant la complétion de Clark et qui ont des complexités spatiales exponentielles dans le pire des cas. De plus, l'énumération est effectuée sur un ensemble restreint de variables du programme logique. Ce qui réduit en général, la complexité temporelle de l'algorithme. En plus de la recherche de modèles stables, cette méthode pourrait générer une sorte d'extra-modèles stables exprimant ainsi l'extension portée à la sémantique des modèles stables.
11h20 -> 11h35 Coffee break
11h35 -> 12h20 — Raskin Jean-Francois, ULB
Titre : Assume Admissible Synthesis.
Abstract :
In this talk, I will show how the notion of admissibility can be used to provide an elegant solution to the synthesis problem for reactive system where the environment is not completely adversarial or when the system is composed of several components. In particular, I will introduce a novel rule for synthesis of reactive systems, applicable to systems made of n components which have each their own objectives. Contrary to previous proposals in the literature, the rule « assume admissible » defines sets of solutions which are rectangular. This property leads to solutions which are robust and resilient, and allows one to synthesize strategies separately for each component.
End: 12h30
Conference : Big Data à la Russe
07/03/2019 à 00h00
Dear all, Dyni / PSD / LIS invite you to the 4th Russo-French Big Data Congress at Toulon, 7th & 8th of march 2019 : https://tinyurl.com/y64jjzkb Free entrance, welcome ! Easy access from TGV station Sincerely, Adeline Paiement & Hervé GlotinSeminaire : CaNa : Nicolas Behr : An introduction to rule algebras and stochastic mechanics for theories of rewriting
19/02/2019 à 14h00
Reference: https://arxiv.org/abs/1807.00785 Abstract: In this talk, without assuming any particular familiarity of the audience with the relevant theory of (M-) adhesive categories, I will provide an introduction to the so-called Double-Pushout (DPO) rewriting framework. Particular emphasis will be given to a novel series of results that concerns a certain form of associativity of the notion of sequential compositions of rewriting rules. In fact, it is this associativity that (via the mathematical framework of rule algebras) permits to make contact between classical notions of manipulations of graphs in combinatorics and statistical physics on the one hand, and the category-theoretical formulation of rewriting theories on the other hand. Some explicit application examples in the field of continuous-time Markov chains based on stochastic DPO-rewriting systems will be presented, including models of dynamical random graph ensembles (such as e.g. a birth-death process on edges of finite graphs).Seminaire : MOVE : Bruno Guillon (CRIStAL, Université de Lille)
07/02/2019 à 10h30
Titre : Finding paths in large graphs Lieu : Salle de réunion du bâtiment modulaire BP5 (en bas de la BU), Luminy Résumé : When dealing with large graphs, classical algorithms for finding paths such as Dijkstra's Algorithm are unsuitable, because they require to perform too many disk accesses. To avoid this cost, while keeping a data structure of size quasi-linear in the size of the graph, we propose to guide the path search with a distance oracle, obtained from a topological embedding of the graph. I will present fresh experimental research on this topic, in which we obtain graph embeddings using learning algorithms from natural language processing. On some graphs, such as the graph of publications of DBLP, our topologically-guided path search allows us to visit a small portion of the graph only, in average. This is joint work with Charles Paperman.Seminaire : CaNa : 22 janvier 2019 à 14h : Sur les délais de communication entre systèmes numériques (microcontrôleurs), BERENGER Cédric
22/01/2019 à 14h00
Résumé : Lors de mon stage de recherche, j’avais développé un algorithme de synchronisation pour de grands réseaux sur la base d’un modèle probabiliste de délais de transmission d’un noeud à l'autre. Lors d’essais avec des systèmes réels, nous sommes tombés sur des observations inattendues qui nous obligent de repenser les modèles, mais qui ouvrent aussi des perspectives d'applications très surprenantes en transformant un défaut en un atout. Salle de réunion du bâtiment modulaire, LuminySeminaire : CaNa : SAT est NP-complet, la preuve !
20/12/2018 à 14h00
Résumé : Ne croyez pas ce que l'on vous a dit, le théorème de Cook-Levin n'est pas si difficile que cela à démontrer... J'ai longtemps admis cette preuve, et après l'avoir lue dans le livre de Sylvain Perifel, j'ai envie de la partager ! Venez ajouter LA brique de base à vos connaissances en complexité, ou simplement réviser :-) Salle du réunion du bâtiment modulaire, LuminySeminaire : DALGO: Thomas Nowak (LRI), vendredi 14 à 10h30
14/12/2018 à 10h30
Title: Approximate Agreement in Dynamic Networks Abstract: Agreeing on a common value in a distributed system is a problem that lies at the heart of many distributed computing problems and occurs in several flavors. Unfortunately, even modest network dynamics already prohibit solvability of exact consensus, where agents have to decide on a single output value that is within the range of the agents' initial values. For many problems (distributed control, clock synchronization, load balancing, ...) it is however sufficient to asymptotically converge to the same value, or decide on values not too far from each other. We study solvability of these consensus variants in highly dynamic networks, provide time complexity results, and present fast algorithms. We then show how the results on dynamic networks are relevant for classical fault-models, such as asynchronous message passing with crashes. The talk is based on joint work with Bernadette Charron-Bost, Matthias Függer, and Manfred Schwarz. Nouvelle salle du conseil, RDC de l'ancienne BU (en entrant à gauche)Seminaire : 5ème demi-journée Pole Calcul
29/11/2018 à 09h30
Dans le cadre du cycle des demi-journées du Pole Calcul du LIS et exceptionnellement aussi du mois de l’IA*, la prochaine et dernière matinée sera autour du thème “Intelligence artificiel et calcul". Les trois intervenants confirmés sont , Gilles Audemard (CRIL) et Cyril Terrioux (LIS) e Leila Amgoud (IRIT).Seminaire : CaNa : Adiabatic methods in quantum control, CHITTARO Francesca
15/11/2018 à 10h00
Résumé : Quantum control is the branch of control theory concerned with quantum systems, that is, dynamical systems at atomic scales, that evolve according to the laws of quantum mechanics.One fundamental issue in quantum control theory is the controllability of quantum systems, that is, whether is it possible to drive a quantum system to a desired state, by means of suitably designed control fields. To cover most theoretical and practical situations, several notion of controllability have been proposed, as, for instance, controllability in the evolution operator, pure state controllability, controllability in population and eigenstate controllability. After a brief introduction on the topic, I will expose some results on the approximate spread controllability of (closed) quantum systems, obtained by means of adiabatic techniques, and taking advantage of the presence of conical intersections between the energy eigenstates. These results have been published in [1],[2].
Adiabatic techniques can be successfully used also to study the dynamics of open quantum systems. In particular, in [3] they have been applied to find an effective description of the evolution of open, weakly coupled quantum systems, where the sub-system of interest dissipate with much slower time scales than the rest of the system.
[1] U. Boscain, F. C. Chittaro, P. Mason, M. Sigalotti Quantum Control via Adiabatic Theory and intersection of eigenvalues IEEE-TAC, (2012) 57, No. 8, 1970--1983
[2] F. C. Chittaro, P. Mason Approximate controllability via adiabatic techniques for the three-inputs controlled Schrödinger equation, SIAM J. Control Optim., (2017), 55(6), 4202–4226.
Salle du réunion du bâtiment modulaire, Luminy
Seminaire : CaNa : Exploring attractor invariance in elementary cellular automata : complexité algorithmique, Stéphanie MacLean
13/11/2018 à 14h00
We are interested in the study of the set of attractors of all 256 Elementary Cellular Automata (ECA) , i.e., one-dimensional, binary 3-neighbourhood cellular automata, dened on an n-cell lattice (n is the length of the automaton).Recent works have studied the invariance of their attractors against dierent update schemes, and how these aect their dynamics. Specically, in [1] was introduced the notion of k-invariance: an ECA rule r is k-invariant if its set of attractors, denoted by Fr(s), remains invariant for all update schemes s having blocks of length at most k (notice that k=1 stands for sequential update schemes, while k = n is the parallel, or synchronous one). In this context, the 1-invariance was studied in [2], where 104 ECA rules showed to have this kind of invariance. In [1] and [3] the authors studied the k-invariance, for 2 < k ≤ n, for all 104 ECA rules above mentioned.
In this work, we explore another notion of attractor invariance "in between ECA rules", we say that two ECA rules u and v are attractor equivalent over a set of update schemes S, if given any s in S, Fu(s) = Fv(s). We begin our study with the 1-invariant rules, searching for equivalences between their sets of attractors, for all 4 ≤ n ≤ 14, so as to have a set of rules that are "candidates" to be attractor equivalent, since we know that if u and v are both 1-invariant ECA rules, then their sets of attractors remain invariant, but not necessarily the same, for all sequential update schemes s. Attractor equivalence gives us new insights of the dynamical behaviour of a rule (and its equivalent rules) under dierent update schemes.
Salle de réunion du bâtiment modulaire, Luminy