Agenda - archives

Conference : Demi-journée du pôle Calcul

19/12/2024 à 09h30

https://demi-journees-pole-calcul.lis-lab.fr/

Speaker : Daniil Kozhemiachenko (LIS, équipe LIRICA)
Title : Logiques paraconsistantes pour le raisonnement sur l’incertitude
Abstract: Pour etre paraconsistante, une logique doit invalider le principe de l’explosion, soit il doivent exister deux formules A et B telles que A&¬A n’implique pas B. Dans cet expose, nous discutons une logique simple paraconsistante de Belnap et Dunn (BD) ainsi que ses augmentations modales et considerons leurs applications au raisonnement sur l’incertitude. Nous traiterons la notion d’incertitude de deux manieres: d’un cote comme une mesure d’incertitude exprimee par une probabilite ou fonction de croyance; d’autre cote comme elle apparait dans les phrases du langage courant telles que «je crois, que…», «je pense, que…», etc. Pour chacun des deux approches a l’incertitude nous proposons sa formalisation a l’aide de BD.

10h15
Speaker : Benjamin Bergougnoux (LIS, équipe COALA)
Title : Neighborhood operator logics: efficient model checking in terms of width parameters
Abstract: In this talk, I will introduce the family of neighborhood operator (NEO) logics which are extensions of existential MSO with predicates for querying neighborhoods of vertex sets. NEO logics have interesting modeling powers and nice algorithmic applications for several width parameters such as tree-width. NEO logics capture many important graphs problems such as Independent Set, Dominating Set and many of their variants. Moreover, some NEO logics capture CNF-SAT via the signed incidence graphs! We can capture more problems by considering various extensions of NEO logics. For example, we can capture problems with global constraints such as Hamiltonian Cycle via the extension of NEO logics with predicates for checking the connectivity/acyclicity of vertex sets. In terms of algorithmic applications, NEO logics seem to be the perfect candidates for capturing many problems that can be solved efficiently in terms of width parameters. This is suggested by the following three results:
For tree-width, the most powerful NEO logics can be model checked in single exponential time in terms of tree-width as implied by a result of Michal Pilipczuk [MFCS 2011]. Jan Dreier, Lars Jaffke and I proved that, for an extension of one NEO logic, we can obtain an efficient model-checking algorithm in terms of several width parameters more general than tree-width such as clique-width, rank-width and mim-width [SODA 2023]. Vera Checkan, Giannos Stamoulis and I are currently proving that the most powerful NEO logic can be solved in single exponential time and polynomial space for tree-depth: the shallow restriction of tree-width. This last result could be interesting in practice where space usage is crucial. I will present these three results after a friendly introduction on width parameters.

Pause Cafe : 11h00 — 11h30

11h30
Speaker : Lê Thành Dũng (Tito) Nguyễn (LIS, équipe LSC)
Title : Algorithmique des graphes pour la combinatoire des preuves en logique linéaire
Abstract: Je présenterai comment un lien entre les « réseaux de preuve » de la logique linéaire et les couplages parfaits, découvert par Christian Retoré, peut être exploité pour obtenir des résultats de complexité sur des problèmes qui intéressent les logicien⋅nes. En particulier, ces outils ont mené à la réfutation de l’équivalence entre deux variantes non-commutatives de la logique linéaire (pomset logic et système BV), équivalence qui était conjecturée depuis deux décennies.

Conference : Séminaire ACRO : Arnaud Mary (16 décembre 14h REU 5.37)

16/12/2024 à 14h00

Arnaud Mary (Université Claude Bernard Lyon 1) Title: Dualization of Hypergraphs with Bounded VC-Dimension 16/12/2024 14h00, salle REU 05.37 (LIS Luminy) Hide abstract A minimal transversal of a hypergraph \cH is an inclusion-wise minimal subset of its vertices that intersects all of its hyperedges. The dual hypergraph of a hypergraph \cH is the hypergraph whose hyperedges consist of all the minimal transversals of \cH . The hypergraph dualization problem asks whether, given a hypergraph \cH and a hypergraph \cG , \cG is the dual hypergraph of \cH . It is known that this problem can be solved in quasi-polynomial time. However, it remains a long-standing open question whether a polynomial-time algorithm exists for this problem. In this presentation, we will show that the problem is solvable in polynomial time if the VC-dimension of either \cH or \cG is bounded. As a consequence, the problem is polynomial-time solvable for any class of hypergraphs that is closed under taking partial subhypergraphs.

Seminaire : Séminaire CANA : Jacopo Surace

10/12/2024 à 16h30

Title : State retrieval beyond Bayes' retrodiction

Salle : 04.05 TPR2

Abstract :

In the context of irreversible dynamics, the meaning of the reverse of a physical evolution can be quite ambiguous. It is a standard choice to define the reverse process using Bayes' theorem, but, in general, this is not optimal with respect to the relative entropy of recovery. In this work we explore whether it is possible to characterise an optimal reverse map building from the concept of state retrieval maps. In doing so, we propose a set of principles that state retrieval maps should satisfy. We find out that the Bayes inspired reverse is just one case in a whole class of possible choices, which can be optimised to give a map retrieving the initial state more precisely than the Bayes rule. Our analysis has the advantage of naturally extending to the quantum regime. In fact, we find a class of reverse transformations containing the Petz recovery map as a particular case, corroborating its interpretation as a quantum analogue of the Bayes retrieval. Finally, we present numerical evidence showing that by adding a single extra axiom one can isolate for classical dynamics the usual reverse process derived from Bayes' theorem.

Seminaire : Séminaire ACRO : Pierre Aboulker (salle REU 04.05 LIS Luminy)

02/12/2024 à 10h00

Pierre Aboulker (ENS, Paris) Title: Clique number of tournaments 02/12/2024 10h00, salle REU 04.05 (LIS Luminy) The dichromatic number of a digraph D is the minimum integer k such that the vertex set of D can be partitioned into k acyclic subdigraphs. It is easy to see that the chromatic number of a graph G is equivalent to the dichromatic number of the digraph obtained from G by replacing each edge with a digon (two anti-parallel arcs). Based on this simple observation, many theorems concerning the chromatic number of undirected graphs have been generalized to digraphs via the dichromatic number. However, no concept analogous to the clique number for digraphs has been available. The purpose of this presentation is to explore such a concept and its relationship with the dichromatic number, mirroring the relationship between the clique number and the chromatic number in undirected graphs. We will focus, in particular, on studying the notion of chi-boundedness.

Seminaire : Séminaire CANA : Alexandre Clément

26/11/2024 à 14h00

Lieu : TPR2 04.05

Titre : Complete Equational Theories for Quantum circuits

Abstract : An equational theory, for quantum circuits or for another graphical language, is a set of equations treated as non-oriented, local rewrite rules. It is said complete when it makes it possible to transform any two equivalent circuits into one another. Having a complete equational theory for quantum circuits can, in principle, help in designing procedures for circuit optimisation, hardware constraint satisfaction, or equivalence testing. From a more abstract perspective, this has a deeper meaning as this gives us an axiomatisation, which in some sense captures the behaviour of quantum circuits. Recently, I together with several collaborators found the first complete equational theory for (ancilla-free) quantum circuits. We further simplified it into just a few simple and intuitive equations, and we proved that this final set of equations is minimal, in the sense that none of the equations can be removed without loosing the completeness. The equational theory contains an equation schema involving an unbounded number of qubits, and we show that this cannot be avoided, although semantically the equations in question are essentially trivial, saying that a 2pi-rotation is the identity. On the contrary, when considering circuits with ancillae and/or qubit discarding, the equation schema can be derived from the other equations, leaving us with a complete equational theory made of equations acting on at most 3 qubits. I will present these results and in particular give the main ideas of the proof of completeness, which relies on a back-and-forth encoding between quantum circuits and another graphical language which was originally dedicated to linear optical circuits. I will also say a few words about some ongoing further work.

Seminaire : Séminaire CANA : Victor Lutfalla

12/11/2024 à 14h00

Title : Ants on the highway

Salle : 04.05 TPR2

Abstract :

Langton's ant is a very simple automaton whose asymptotic behaviour has been conjectured in the 80s but still evades formal proof. In this talk I will present recent advances on the asymptotic behaviour of generalized ants. Langton's ant is a very simple automaton evolving with a binary configuration of the square grid. When the ant enters a white (or 0) cell it turns a left half-turn, flips the state of the cell and moves one step forward; when it enters a black (or 1) cell it turns a right half-turn, flips the state of the cell and moves one step forward. From the initial 0-uniform configuration, Langton's ant has a "chaotic" transient phase during 10^4 steps, then enters a periodic behaviour with a drift: in 104 steps it moves by (±2,±2). This periodic behaviour with a drift is called highway. It has been conjectured that from any almost 0-uniform configuration (finitely many non-zero cells), Langton's ant has the same behaviour : a "chaotic" transient phase and then the highway of period 104 and drift (±2,±2). A simple generalisation of Langton's ant, takes a directing word w on alphabet L,R. The generalized ant w evolves with a square grid where the cells have states between 0 and |w|-1. When the ant w arrives on the cell in state k, if the k-th letter of w is a L it turns left (or right otherwise), increments the cell state by 1 modulo |w| and moves on step forward. We study the asymptotic behaviour of such generalized ants and in particular we prove that: - there exist infinite families of generalized ants with more than one possile highway behaviour - there exist ants with infinitely many different highway behaviours - in particular the "speed" of a highway of the ant w (on an almost-0-uniform configuration) is not determined by the directing word w.

Seminaire : Séminaire CANA : Shuwen Kan

05/11/2024 à 15h00

Lieu : online and TPR2 04.05

Titre : A Scalable Quantum Circuit Cutting in a Distributed System

Abstract : Despite rapid advancements in quantum computing, current systems remain limited by qubit count and quality. To address these limitations, recent efforts focus on multi-node quantum systems connecting smaller devices. While future approaches aim to leverage quantum channels for coupling, current methods primarily rely on circuit cutting techniques that leverage a hybrid quantum-classical system. It partitions large circuits into smaller, independently executable fragments and reconstructs them classically. However, existing methods face challenges such as increased search times with circuit complexity and inefficient resource allocation across multi-node systems. To address these issues, we introduce FitCut, a novel graph-based framework that employs a community-based, bottom-up strategy to identify optimal cut points based on resource constraints. Additionally, it incorporates a scheduling algorithm that optimizes resource allocation across workers. Implemented within the Qiskit framework, FitCut has been extensively evaluated, demonstrating significant improvements over existing tools such as the Qiskit Circuit Knitting Toolbox. Specifically, FitCut reduces search time by factors ranging from 3 to 2000 and enhances resource utilization rates by up to 388% on the worker side, resulting in a system-wide improvement of 286% in accumulated circuit depth.

Conference : Séminaire ACRO : Jean-Florent Raymond (4.05, 14h)

04/11/2024 à 14h00

*A Ramsey-type theorem for traceable graphs, revisited* Consider a graph G with a path P of order n. What conditions force G to also have a long induced path? As complete bipartite graphs have long paths but no long induced paths, a natural restriction is to forbid some fixed complete bipartite graph Ktt as a subgraph. In this case we show that G has an induced path of order (\log \log n)^{1/5-o(1)}. This is an exponential improvement over a result of Galvin, Rival, and Sands (1982) and comes close to a recent upper bound of order O((\log \log n)²).

Seminaire : Analyse de documents juridiques

09/10/2024 à 14h30

Présentation des travaux de Laura Duparc et des travaux d'Adrian Chifu en collaboration avec Eric San-Juan

Seminaire : Séminaire CANA - Tomáš Gonda

08/10/2024 à 14h00

Lieu : TPR2 04.05

Titre : A Framework for Universality in Physics, Computer Science, and Beyond

Abstract : Turing machines and spin models share a notion of universality according to which some simulate all others. We set up a categorical framework for universality which includes as instances universal Turing machines, universal spin models, NP completeness, top of a preorder, denseness of a subset, and others. By identifying necessary conditions for universality, we show that universal spin models cannot be finite. We also characterize when universality can be distinguished from a trivial one and use it to show that universal Turing machines are non-trivial in this sense. We leverage a Fixed Point Theorem inspired by a result of Lawvere to establish that universality and negation give rise to unreachability (such as uncomputability). As such, this work sets the basis for a unified approach to universality and invites the study of further examples within the framework.

Conference : Atelier : Le traitement automatique des langues (TAL) à l'ère de l'IA générative, des sciences cognitives et de la transformation sociétale

01/10/2024 à 14h30

Le LIS et AMU sont associés à un partenariat France/Canada à travers le GDR TAL de CNRS Sciences Informatiques qui co-organise un évènement au Mila à Montréal portant sur la Traitement Automatique des Langues du 1er au 3 octobre. La participation à distance est possible sur le lien vidéo : https://www.youtube.com/@mila-quebecartificialintel8371/live Plus d'information : https://mila.quebec/fr/evenement/atelier-le-traitement-du-langage-naturel-nlp-a-lere-de-lia-generative-des-sciences

Seminaire : Séminaire ACRO : Simon Vilmin REU 04.05 (LIS Luminy)

30/09/2024 à 10h00

Simon Vilmin (LIS, Aix-Marseille Université) Title: Séparation par demi-espaces dans la convexité monophonique 30/09/2024 10h00, salle REU 04.05 (LIS Luminy) Une convexité sur un univers fini X est une collection de sous-ensembles de X, dits convexes, contenant le vide, X, et fermée par intersection. Cette notion de convexité généralise la convexité classique dans IR^d et capture également de nombreux objets tels que les convexes d'une géométrie convexe, les flats d'un matroïde, les attracteurs d'un réseau booléen, ou encore les modèles d'une CNF de Horn. Nous serons intéressé ici par la grande famille des convexités définies à partir de graphes. Dans une convexité, un convexe H dont le complémentaire X \ H est convexe est appelé un demi-espace. Deux sous-ensembles A et B de X sont alors dits séparables s'il existe une paire de demi-espaces (H, X \ H) telle que A soit inclus dans H et B dans X \ H. A nouveau, cette notion de séparabilité généralise la séparabilité de deux convexes (disjoints) de IR^d, et a été très étudiée d'un point de vue structurel--via des axiomes de séparation--dans les convexités de graphes et les convexités en général. Dans cet exposé on s'intéressera plutôt au problème de décision associé pour la convexité monophonique, c.-à.-d la convexité induite par les chemins sans cordes d'un graphe. Le problème se formule ainsi : étant donnés un graphe G et deux ensembles de sommets A et B, décider de la séparabilité de A et B. Bien que le problème soit NP-complet pour la convexité géodésique--la convexité des plus courts chemins--on montrera qu'il peut être résolu en temps polynomial pour la convexité monophonique.

Seminaire : Séminaire CANA : Pacôme Perrotin

24/09/2024 à 14h00

Lieu : TPR2 04.05

Titre : Recent advancements in consensus problems over automata networks

Abstract : Consensus problems consider distributed systems (mostly cellular automata and automata networks) which are able to converge from any initial configuration to a uniform configuration, usually where the uniform value of the final configuration holds some information about the initial configuration. We present recent progress done in the last year regarding some variations of the problems, namely a new family of solutions to the parity and synchronisation problems in automata networks, and a cellular automata which solves the density problem using an intermediary alphabet and a sequential update schedule. We also discuss some recent negative results regarding the density problem, and some ongoing attempts at characterising all linear solutions to the parity problem.

Seminaire : Séminaire ACRO : Pascal Préa salle REU 04.05 (LIS Luminy)

16/09/2024 à 10h00

Pascal Préa (LIS, Aix-Marseille Université) Title: Un algorithme efficace pour reconnaitre les dissimilarités dont tous les chemins de tous les arbres de longueur minimale sont Robinsoniens 16/09/2024 10h00, salle REU 04.05 (LIS Luminy) Étant donné une dissimilarité d sur un ensemble X, un arbre T=(X,E) est R-compatible avec (X,d) si pour tous x, z dans X et tout y sur le chemin entre x et z, d(x,z)≥ max{d(x,y), d(y,z)}. Si T est compatible avec (X,d), alors T est un arbre de longueur minimale (ALM — MST) de (X,d). Étant donné (X,d) avec |X|=n, nous présenterons dans cet exposé un algorithme en O(n^2) pour vérifier si un ALM donné T est compatible (avec (X,d)) et un algorithme en O(n^3) qui détermine si tous les ALM de (X,d) sont R-compatibles.

Seminaire : Séminaire CANA : Rocco Ascone (Università degli Studi di Trieste)

16/07/2024 à 16h00

Lieu : online et TPR2 04.05

Titre : Complexity of the dynamics of resource-bounded reaction systems

Abstract : Reaction systems are discrete dynamical systems that model biological processes in living cells using finite sets of reactants, inhibitors, and products. Synchronous Boolean networks can be viewed as a generalisation of this model.

In this talk, we will investigate the computational complexity of a comprehensive set of problems related to the existence of fixed points and attractors in three constrained classes of reaction systems: inhibitorless, reactantless and additive (in which each reaction involves at most one reactant and no inhibitors).

We will see that although the absence of reactants or inhibitors simplifies the system’s dynamics, it does not always lead to a reduction in the complexity of the considered problems for inhibitorless/reactantless reaction systems. Furthermore, all considered problems are polynomially solvable in additive systems using a polynomially computable graph representation.

I will also introduce some open questions and future research directions.

Rencontre : Journées stagiaires équipe DALGO

02/07/2024 à 09h30

Chaque année, notre équipe organise des journées afin que tous les stagiaires puissent présenter leurs travaux. Cette année cette journée aura lieu dans la salle A2 du CIRM (sur le site de Luminy). Vous trouverez le planning des exposés ci-dessous :

- 9h30-9h50: Manal CHABANE, Schéma de signature numérique avec l’algorithme de cryptographie asymétrique RSA
- 9h50-10h10: Abanoub ABDELSHAHID, Simulateur pour l’algorithme distribué de consensus Raft
- 10h10-10h30: Dang Dinh NGUYEN, Sécurité des méta-données dans les applications de messagerie instantanée
- 11h00-11h30: Anatole GROSDOY, Énumération lexicographique d’ensembles indépendants maximaux
- 11h30-12h: Pierre DURIEUX, Énumération d’objets métriques dans les graphes
- 14h00-14h30: Baksi SOUMIL, Wait-free implementation of 2-window-register object with swap objects
- 14h30-15h: Yao David KOLEGAIN, Lattice agreement problem in asynchronous systems with Byzantine failures

Conference : Multimodal Information Processing: Some recent NLP applications

24/06/2024 à 10h00

Multimodal information processing deals with the efficient usage of information available in different modalities such as audio, video, text, etc. for solving various task applications of real life. This talk will discuss how the multimodal information extracted from different modalities can help improve different tasks of summarization, hate speech detection, and complaint mining. Multimodal information collected from videos, images, and texts can be utilized to generate a summary. Images and texts collected from Amazon reviews are utilized to develop aspect-based multimodal complaint detection systems in a multi-task setting where sentiment and emotion information are utilized as auxiliary tasks. Memes collected from social media are utilized to detect hate speech in a multitasking setting where sentiment, emotion, and sarcasm detection are utilized as auxiliary tasks. This talk will highlight the different applications of multimodal information processing in solving different NLP tasks.

Seminaire : Séminaire COALA : Benjamin BERGOUGNOUX (Warsaw University)

19/06/2024 à 15h00

Lieu : Salle de réunion de l'équipe COALA

Titre : Neighborhood operator logics: efficient model checking in terms of width parameters

Résumé : In this talk, I will introduce the family of neighborhood operator (NEO) logics which are extensions of existential MSO with predicates for querying neighborhoods of vertex sets. NEO logics have interesting modeling powers and nice algorithmic applications for several width parameters such as tree-width. NEO logics capture many important graphs problems such as Independent Set, Dominating Set and many of their variants. Moreover, some NEO logics capture CNF-SAT via the signed incidence graphs! We can capture more problems by considering various extensions of NEO logics. For example, we can capture problems with global constraints such as Hamiltonian Cycle via the extension of NEO logics with predicates for checking the connectivity/acyclicity of vertex sets. In terms of algorithmic applications, NEO logics seem to be the perfect candidates for capturing many problems that can be solved efficiently in terms of width parameters. This is suggested by the following three results: - For tree-width, the most powerful NEO logics can be model checked in single exponential time in terms of tree-width as implied by a result of Michal Pilipczuk [MFCS 2011]. - Jan Dreier, Lars Jaffke and I proved that, for an extension of one NEO logic, we can obtain an efficient model-checking algorithm in terms of several width parameters more general than tree-width such as clique-width, rank-width and mim-width [SODA 2023]. - Vera Checkan, Giannos Stamoulis and I are currently proving that some NEO logic can be solved in single exponential time and polynomial space for tree-depth: the shallow restriction of tree-width. This last result could be interesting in practice where space usage is crucial. I will present these three results after a friendly introduction on width parameters.

Seminaire : Séminaire CANA - Maximilien Gadouleau (Durham University)

18/06/2024 à 14h00

Lieu : TPR2 04.05

Titre: Les réseaux Booléens et leurs trapspaces

Résumé : Un réseau Booléen est un outil simple pour modéliser un réseau d'entités qui interagissent. Chaque entité a un état dans {0,1} qui évolue selon une règle déterministe. Mathématiquement, un réseau Booléen est une fonction f du cube {0,1}^n dans lui-même. Un "trapspace" d'un réseau Booléen f est un sous-cube clos par f. Les trapspaces sont importants car ils représentent des états stabilisés au cours de l'évolution du réseau. Un trapspace est dit principal s'il est le plus petit trapspace contenant une configuration x de {0,1}^n. Dans cet exposé, nous classifions les collections de trapspaces et les collections de trapspaces principaux des réseaux Booléens. Les trapspaces de f peuvent être représentés à l'aide d'un autre réseau, que l'on nomme réseau trapping. Nous montrons aussi que les réseaux trappings ont des propriétés dynamiques très intéressantes. Travaux en collaboration avec Loïc Paulevé et Sara Riva.

Seminaire : Séminaire ACRO : Aurélie Lagoutte (17/06 REU 4.05 14h)

17/06/2024 à 14h00

Séminaire ACRO : Aurélie Lagoutte (17/06 REU 4.05 14h) Luminy Titre : Online algorithm for the Canadian Traveler Problem on outerplanar graphs Résumé : Given a graph G and two vertices s and t, the Canadian Traveler Problem consists in finding a "short" path between s and t in G, when some unexpected obstacles (for example, snow falls) can block up to k edges, for some input integer k. The status (open or blocked) of each edge is discovered only when walking through one of its extremities, and the traveler has to decide at each step of his walk the next vertex to visit. The goal is to minimise the ratio between the length of the walk from s to t that the traveler actually performs, and the actual distance from s to t he would have traversed knowing the blocked edges in advance. Even though the optimal competitive ratio is 2k + 1 even on unit-weighted planar graphs of treewidth 2, we design a polynomial-time strategy achieving competitive ratio 9 on unit-weighted outerplanar graphs, and this ratio is best possible. Finally, we show that it is not possible to achieve a constant competitive ratio (independent of G and k) on weighted outerplanar graphs.

WorkShop : Journées Apprentissage Signal Image, 17-18 juin

17/06/2024 à 09h00

Les Premières Journées Apprentissage Signal Image du LIS auront lieu les 17 et 18 juin à Châteauneuf le Rouge au pied de la Sainte Victoire.

Objectif :

L'objectif est de contribuer à l'animation scientifique autour de l'interface Apprentissage/Signal/Image au sein du LIS dans un environnement propice.

Un descriptif du programme prévisionnel, et d'autres informations utiles, sont disponibles à l'adresse suivante : https://sync.lis-lab.fr/index.php/s/CQWxsC9wWqRFHf7.

Equipe organisatrice :

Séverine Dubuisson (I&M)
Sébastien Paris (DINY)
Xavier Luciani et Frédéric Bouchara (SIIM)
Valentin Emiya (QARMA)

Seminaire : Séminaire I&M - Karim Seghouane (University of Melbourne, Australia)

11/06/2024 à 14h00

Titre :Learning Robust and Sparse Principal Components
Lieu : Luminy, TPR2 salle de réunion 04.05

ABSTRACT :
In this seminar, novel robust principal component analysis (RPCA) methods to exploit the local structure of datasets are presented. The proposed methods are derived by minimizing the α-divergence between the sample distribution and the Gaussian density model. The α−divergence is used in different frameworks to represent variants of RPCA approaches including orthogonal, non-orthogonal, and sparse methods. We show that the classical PCA is a special case of the proposed methods where the α−divergence is reduced to the Kullback-Leibler (KL) divergence. Furthermore, I shown in simulations that the proposed approaches recover the underlying principal components (PCs) by down-weighting the importance of structured and unstructured outliers. Using simulated data, it is shown that the proposed methods can be applied to fMRI signal recovery and Foreground-Background (FB) separation in video analysis. Results on real world problems of FB separation as well as image reconstruction are also presented.

BIOGRAPHIC:
Dr. Abd-Krim (Karim) Seghouane is a faculty member in the School of Mathematics and Statistics at the University of Melbourne, Australia.
Prior to this, he was a Senior Lecturer at the Department of Electrical and Electronic Engineering at the same University. He received his PhD from Paris Sud University, now known as University of Paris-Saclay, France. Upon completing his PhD, he worked as postdoctoral researcher at INRIA Rocquencourt, France and then as a researcher and subsequently as a senior researcher with National ICT Australia (NICTA). While at NICTA he was also an adjunct faculty member with the College of Engineering and Computer Science at the Australian National University (ANU). Dr. Seghouane’s research interests are in the areas of statistical signal and image processing, machine learning and artificial intelligence. His current research applications are focused on medical imaging and physiological signal analysis. He has received fellowships from the Australian Research Council, the Japanese Society for the Promotion of Science, the Australian Academy of Science and the French National Institute for Research in Digital Science and Technology.
Dr. Seghouane is currently an elected member of the IEEE Signal Processing Society Computational Imaging Technical Committee (CITC) and prior to that he was an elected member of the IEEE Signal Processing Society Machine Learning for Signal Processing Technical Committee (MLSPTC). While he was a member of the IEEE MLSPTC, he was also the chair of the data competition sub-committee. He was the General Co-Chair of the 2014 IEEE Workshop on Statistical Signal Processing and of the 2021 IEEE Workshop on Machine Learning for signal Processing, Gold Coast, Australia, the Data Competition Co-Chair of the 2017 and 2018 IEEE Workshop on Machine Learning for Signal Processing, Tokyo, Japan and Aalborg, Denmark, and the Organization Co-Chair of the 2017 IEEE International Symposium on Biomedical Imaging, Melbourne, Australia. He has served as an Associate Editor on the editorial board of the IEEE Transactions on Image Processing, from 2014 to 2018; and since 2018, he serves as a Senior Editor Area. He has also served on the editorial board of the IEEE Transactions on Signal Processing as an Associate Editor, from 2017 to 2021.

Seminaire : Séminaire I&M - Manu Jain (MSKCC, New York)

11/06/2024 à 10h00

Titre :Advancements in Dermatological Diagnosis: Harnessing Artificial Intelligence, Deep Learning, and 3D Reconstructions in Noninvasive Skin Imaging
Lieu : Luminy, TPR2 salle de réunion 04.05

ABSTRACT :
Noninvasive skin imaging techniques, including reflectance confocal microscopy (RCM) and optical coherence tomography (OCT), are transforming the landscape of skin cancer diagnosis and management. However, the current reliance on human expert readers for diagnosis presents limitations. Artificial intelligence (AI), deep learning, and 3D reconstructions are revolutionizing healthcare by enhancing diagnostic and prognostic capabilities. In dermatology, their integration with noninvasive skin imaging holds significant promise for improving the accuracy and efficiency of disease diagnosis and monitoring. They can guide technicians during image acquisition, remove artifacts, and enhance image quality. Furthermore, they can assist dermatologists in identifying regions of interest, facilitating automated lesion detection, classification, and monitoring with heightened accuracy and efficiency. Automated detection would further enable widespread utilization of these techniques.

BIOGRAPHIC:
Dr. Manu Jain is an Associate Attending at Memorial Sloan Kettering Cancer Center and an Assistant Professor at Weill Cornell Medicine in the Department of Dermatology. Dr. Jain is as a Founding Board Member (Vice President) of the American Confocal Group and a Founding Member of the Cutaneous Imaging Expert Resource group (AAD). She is currently President of the Noninvasive Skin Imaging Group of the Americas (NISIA). Additionally, she chairs the session “Photonics in Dermatology and Plastic Surgery” at the Photonics West (SPIE) annual meeting and contributes as a Board Member of International Confocal Group. She is the founder and Course Director of the MSKCC Annual Confocal CME-accredited course. Dr. Jain is as a pathologist and an optical imaging specialist over 14 years of experience in techniques such as multiphoton microscopy, confocal microscopy, optical coherence tomography (OCT), and multimodal devices. Her extensive publication record underscores her significant contributions to this specialized field. Dr. Jain is dedicated to training the next generation of clinicians in noninvasive imaging. Her goal is to revolutionize the early detection of skin cancers by reducing morbidity and mortality. Dr. Jain has been an invited speaker at numerous national and international congresses.

Seminaire : Séminaire CANA - Ravi Kunjwal (LIS)

04/06/2024 à 14h00

Lieu : TPR2 04.05

Titre : Nonclassicality in correlations without causal order

Résumé : A Bell scenario can be conceptualized as a "communication" scenario with zero rounds of communication between parties, i.e., although each party can receive a system from its environment on which it can implement a measurement, it cannot send out any system to another party. Under this constraint, there is a strict hierarchy of correlation sets, namely, classical, quantum, and non-signalling. However, without any constraints on the number of communication rounds between the parties, they can realize arbitrary correlations by exchanging only classical systems. We consider a multipartite scenario where the parties can engage in at most a single round of communication, i.e., each party is allowed to receive a system once, implement any local intervention on it, and send out the resulting system once. Taking our cue from Bell nonlocality in the "zero rounds" scenario, we propose a notion of nonclassicality---termed antinomicity---for correlations in scenarios with a single round of communication. Similar to the zero rounds case, we establish a strict hierarchy of correlation sets classified by their antinomicity in single-round communication scenarios. Since we do not assume a global causal order between the parties, antinomicity serves as a notion of nonclassicality in the presence of indefinite causal order (as witnessed by causal inequality violations). A key contribution of this work is an explicit antinomicity witness that goes beyond causal inequalities, inspired by a modification of the Guess Your Neighbour's Input (GYNI) game that we term the Guess Your Neighbour's Input or NOT (GYNIN) game. Time permitting, I will speculate on why antinomicity is a strong notion of nonclassicality by interpreting it as an example of fine-tuning in classical models of indefinite causality.
This is based on joint work with Ognyan Oreshkov, arXiv:2307.02565.

Rencontre : [Explore] Speed-searching grand public sur la Grande Roue

02/06/2024 à 14h00

Dimanche 2 juin de 14h à 17h à l'Escale Borély, embarquez dans la grande roue et discutez en tête-à-tête pendant 10 minutes d'IA avec Hachem Kadri, le temps d’un tour gratuit ! Plus d'information sur le site d'Explore.

Rencontre : [Rencontres de rue] comprendre les décisions de l'IA

02/06/2024 à 14h00

Venez rencontrer dans les rues marseillaises Ronan Sicre pour une animation sur l'explication des décisions prises par l’IA mercredi 29 mai de 14h à 18h Place François Mireur devant l’Alcazar et dimanche 2 juin de 14h à 18h sur l'esplanade de l’Escale Borély ! Plus d'information sur le site d'Explore.

Seminaire : Séminaire I&M - Adrien JULIA

31/05/2024 à 14h00

Titre : 3D Segmentation of Mouse Brain Cell Nuclei Imaged Using Light Sheet Microscopy
Lieu : Luminy, TPR2 salle de réunion 04.03.

Résumé :
Medical image segmentation has been a widely studied field in the computer vision community. Several methods have been developed using both conventional and deep learning approaches. Among deep learning methods, U-Net is still one of the most used architectures, based on the use of a convolutional auto-encoder. Several modalities need to be tackled when dealing with biological image processing. We focus our study on two important aspects: the need for annotated datasets to train a neural network, and the need to perform 3D segmentation.
Light Sheet Fluorescence Microscopy provides high-quality images of neural circuitry, enabling the scanning of an entire mouse brain quickly. Analyzing the cell nuclei and the whole neural structure is a challenging task, involving the automatic extraction of both cell nuclei and neurons. Neurons can have a wide variety of shapes and are better captured using 3D imaging. Cell nuclei segmentation in the case of wide-field microscopy is still a challenging task, as the size of nuclei can sometimes be only a couple of pixels. These nuclei can also aggregate, making it even more difficult to differentiate them.

Rencontre : [Explore] Speed-searching grand public à l'Alcazar

29/05/2024 à 14h00

Discutez en tête-à-tête d'IA avec Hachem Kadri mercredi 29 mai de 14h à 17h à l'Alcazar! Plus d'information sur le site d'Explore.

Rencontre : [Rencontres de rue] comprendre les décisions de l'IA

29/05/2024 à 14h00

Seminaire : Soutenance de thèse Alexandre Marin GMOD

21/05/2024 à 10h30

21 mai à 10h30 à Polytech Luminy, amphi A Titre : Maillage polyédrique de volumes 3D optimisé pour la simulation en géosciences Résumé : L’usage de plus en plus répandu de l’informatique graphique engendre de nouveaux problèmes et besoins. Notamment, la généralisation des simulations numériques occasionne aussi de nouveaux défis. Compte tenu des inconvénients des maillages tétraédriques et hexa-dominants, et puisque que les méthodes du type Éléments Finis sont limitées à des maillages contenant des cellules de topologies bien précises (par exemple hexaèdres et leurs dégénérescences), des travaux récents sur les simulations numériques ont développé des méthodes applicables à des maillages plus généraux. La famille des volumes finis non linéaires, et plus particulièrement les méthodes HMM, sont des exemples de telles généralisations. Initialement élaborées pour les maillages en géosciences classiques, ces méthodes peuvent en fait être appliquées à une plus grande classe de maillages, qui est celle des maillages polyédriques. Les maillages polyédriques sont de bons candidats pour simultanément remplir les deux conditions suivantes : réduire le nombre de cellules et contrôler leur géométrie pour améliorer la stabilité et les performances des simulations. La génération de diagrammes de Voronoï est une des façons les plus connues de paver un domaine de l’espace. Pour contrôler le rapport de forme des cellules de ces diagrammes de Voronoï, les travaux en pointe définissent une énergie, appelée fCVT, dont la minimisation permet de maîtriser la densité et l’anisotropie de tels pavages de Voronoï. Cependant, les approches proposées ne sont pas toujours efficaces et restent difficiles à mettre en oeuvre (pour des raisons techniques, l’optimisation de l’énergie requiert une discrétisation du volume d’intérêt et du champ d’anisotropie). Notre contribution est triple : • premièrement, nous introduisons une structure de données pour encoder de tels maillages polyédriques efficacement (aussi bien du point de vue de la consommation de mémoire que du temps d’accès aux données); • ensuite, nous nous concentrons sur le calcul de diagrammes de Voronoï anisotropes. Nous introduisons et prouvons une expression du gradient ∇fCVT pour un champ continu d’anisotropie. Contrairement aux méthodes modernes, nous obtenons une méthode (dite « exacte » dans la suite) qui n’exige aucune discrétisation du domaine d’intérêt, et par conséquent qui ne dépend pas de la géométrie du maillage de ce dernier. Dernièrement, nous introduisons une heuristique hiérarchique pour accélérer et paralléliser le calcul de pavages polyédriques anisotropes. Pour valider cette approche, nous donnons des résultats qualitatifs et quantitatifs, et nous comparons avec une autre méthode récente; • troisièmement, nous examinons les questions soulevées par la mise en conformité de tels maillages : ces pavages devraient se conformer à des surfaces décrivant des interfaces de nature géologique (failles et horizons). Vous espérant nombreux. A très bientôt

Seminaire : Séminaire I&M - Sabrine djedjiga OUCHERIF

17/05/2024 à 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é :

CONTEXTE
Depuis plusieurs décennies, la reconnaissance des expressions faciales est reconnue comme une méthode essentielle pour l'analyse approfondie des émotions humaines, constituant un pilier de l'analyse comportementale moderne. Aujourd'hui, notre compréhension de ce domaine est renforcée par l'intégration de la recherche académique avec des technologies avancées. 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), explore des applications de ces méthodes au marketing. Grâce aux caméras plénoptiques, qui capturent l'intensité et la direction des rayons lumineux, nous obtenons des images multiperspectives en une seule prise [1, 2]. Ces images, en facilitant la création de cartes de profondeur détaillées, améliorent notre capacité à analyser les nuances des expressions faciales, enrichissant ainsi notre compréhension des réactions émotionnelles des consommateurs.

OBJECTIFS
L'objectif final de ce projet est d'analyser le comportement des personnes dans un espace de vente, en mettant l'accent sur l'étude et la reconnaissance des expressions faciales. Pour ce faire, nous utiliserons des caméras plénoptiques, qui fournissent des images de sous-ouverture, des images total focus ainsi que des cartes de profondeur. Ces divers types d'images nous permettront de capturer des données riches et variées sur les interactions des consommateurs. Nous nous appuierons sur des architectures innovantes combinant des réseaux de neurones convolutifs (CNN) et récurrents (RNN) pour extraire les informations spatiales et angulaires contenues dans les données capturées par les caméras plénoptiques. L'approche de fusion multimodale sera utilisée pour intégrer et traiter ces différentes informations, afin de fournir une analyse comportementale précise et approfondie des consommateurs.

[1] T. -W. Shen et 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.

Conference : Séminaire ACRO : Frédéric Havet (salle REU 04.05 LIS Luminy)

06/05/2024 à 10h00

Frédéric Havet (INRIA, Sophia Antipolis) Title: Inversions in oriented graphs 06/05/2024 10h00, salle REU 04.05 (LIS Luminy) The inversion of a set X of vertices in an oriented graph consists in reversing the direction of all arcs of the subdigraph induced by X. This generalization of single arc reversal introduced by Belkhechine et al. yields a notion of distance between orientations of a same graph where two orientations are at distance one if and only if there is a set X whose inversion transforms one into the other. First we will discuss the minimum number of inversions required to make an oriented graph acyclic, and in particular a proof of the existence of n-vertex oriented graphs at distance n-o(n) of any acyclic orientation. We also investigate the minimum number of inversions needed to make an oriented graph k-strong, especially in the case of tournaments. Finally, we show various bounds on the maximum distance between two orientations of a same graph. This gives an undirected graph parameter that we show to be tied to several known parameters, including the star chromatic number and acyclic chromatic number. We also prove that two orientations of a same planar graph are at distance at most 12. All these results relied on an algebraic point of view on this problem that allows us to use linear algebra in the field with two elements. This talk on joint papers with Guillaume Aubian, Julien Duron, Florian Horsch, Felix Klingelhoefer, Nicolas Nisse, Clément Rambaud and Quentin Vermande.

Seminaire : Séminaire ACRO : Oscar Defrain, salle REU 04.05 (LIS Luminy)

29/04/2024 à 10h00

Oscar Defrain (LIS, Aix-Marseille Université) Title: Énumération Algorithmique VI. Flipping method. 29/05/2024 10h00, salle REU 04.05 (LIS Luminy) Cet exposé est le sixième d’une série d’exposés sur le thème de l’énumération algorithmique où sont présentés différentes techniques, résultats et problèmes ouverts du domaine. Dans cet épisode, on s’intéressera à un cas particulier de supergraph method multi-sources qui concerne l’énumération des dominants minimaux dans les graphes. Cette technique, appelée « flipping method » se base sur la génération de dominants minimaux depuis les stables maximaux par échange de sommets ayant pour but de réduire le nombre d’arête.

Seminaire : Séminaire I&M - Mira Razafindrambao

26/04/2024 à 14h00

Titre :Apprentissage profond pour le diagnostic du cancer du pancréas à partir d'images écho-endoscopiques
Lieu : Luminy, TPR2 salle de réunion 04.03.
Résumé :
En 2020, le cancer du pancréas était le septième cancer le plus mortel au monde. Au vu de son taux de diagnostic qui ne diminue pas contrairement à d'autres cancers mortels comme le cancer du sein, il est prédit qu'en 2025 le cancer du pancréas devienne le troisième cancer le plus mortel au monde. L'idée d'utiliser l'intelligence artificielle pour l'aide au diagnostic n'est pas neuve. Toutefois l'examen principalement utilisé afin de diagnostiquer le cancer du pancréas est l'échographie endoscopique, une modalité qui reste peu étudiée dans le domaine de l'IA pour l'imagerie médicale.
Les travaux en cours ont donc pour objectif de créer un modèle permettant de détecter la présence ou non d'une tumeur sur une image d'échographie. Ce type de tâche est aujourd'hui majoritairement traité avec des modèles de deep learning. Cependant utiliser le deep learning fait émerger un autre problème : celui de l'interprétabilité et de la confiance de l'utilisateur final.
Dans cette présentation seront expliqués le contexte et les enjeux de ce travail, le type de données utilisées et ses spécificités, quel est l'avancement du projet ainsi que les étapes envisagées pour la suite.

Seminaire : Séminaire ACRO : Jean-Florent Raymond (CNRS, LIP, Lyon)

15/04/2024 à 14h30

Jean-Florent Raymond (CNRS, LIP, Lyon) Title: Local certification of geometric graph classes 15/04/2024 14h30, salle REU 04.05 (LIS Luminy) Hide abstract The goal of local certification is to locally convince the vertices of a graph G that G satisfies a given property. A prover assigns short certificates to the vertices of the graph, then the vertices are allowed to check their certificates and the certificates of their neighbors, and based only on this local view, they must decide whether G satisfies the given property. If the graph indeed satisfies the property, all vertices must accept the instance, and otherwise at least one vertex must reject the instance (for any possible assignment of certificates). The goal is to minimize the size of the certificates. In this paper we study the local certification of geometric and topological graph classes. While it is known that in n-vertex graphs, planarity can be certified locally with certificates of size O(log n), we show that several closely related graph classes require certificates of size Ω(n). This includes penny graphs, unit-distance graphs, (induced) subgraphs of the square grid, 1-planar graphs, and unit-square graphs. These bounds are tight up to a constant factor and give the first known examples of hereditary (and even monotone) graph classes for which the certificates must have linear size. For unit-disk graphs we obtain a lower bound of Ω(n^{1−δ}) for any δ>0 on the size of the certificates, and an upper bound of O(n log n). The lower bounds are obtained by proving rigidity properties of the considered graphs, which might be of independent interest.

Seminaire : Séminaire ACRO : Oscar Defrain (salle REU 04.05)

08/04/2024 à 10h00

Oscar Defrain (LIS, Aix-Marseille Université) Title: On the enumeration of signatures of XOR-CNF’s 08/04/2024 10h00, salle REU 04.05 (LIS Luminy) Given a CNF formula φ with clauses C1,…,Cm over a set of variables V, a truth assignment a : V→{0,1} generates a binary sequence σ(a)=(C1(a),…,Cm(a)), called a signature of φ, where Ci(a)=1 if clause Ci evaluates to 1 under assignment a, and Ci(a)=0 otherwise. Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration. In a recent paper, Bérczi et al. interestingly proved that generating signatures of a CNF is tractable despite the fact that verifying a solution is hard. They also showed the hardness of finding maximal signatures of an arbitrary CNF due to the intractability of satisfiability in general. Their contribution leaves open the problem of efficiently generating maximal signatures for tractable classes of CNFs, i.e., those for which satisfiability can be solved in polynomial time. Stepping into that direction, we completely characterize the complexity of generating all, minimal, and maximal signatures for XOR-CNFs.

Seminaire : Séminaire CANA : Pedro Balbi

02/04/2024 à 14h00

Où : salle 04.05, bât TPR2, Luminy

Titre : Solving the parity problem in automata networks

Résumé : The parity problem is a classical binary benchmark for addressing the computational ability and limitations of automata networks. It refers to conceiving a local rule to allow deciding whether the number of 1-states in the nodes of an arbitrary network is an odd or even number, without global access to the nodes. In its standard formulation, the automata network has an odd number of nodes whose states, arranged as a cyclic configuration, should converge to a fixed point of all 0s, if the initial configuration has an even number of 1s, or to a fixed point of all 1s, otherwise. It has been shown that a local rule alone is able to solve the problem in this formulation. In this talk I will review some solutions available for the problem, with a focus on recent solutions we provided on a non-circulant graph with synchronous update.

Seminaire : Séminaire I&M - DE SOUSA SILVA, Raul Alfredo

29/03/2024 à 14h00

Titre :Modélisation du comportement complexe autistique chez la souris en utilisant la vision par ordinateur et des approches d'apprentissage profonde
Lieu : Luminy, TPR2 salle de réunion 04.03.
Résumé :
Le Trouble du Spectre Autistique (TSA) est une maladie neurologique et développementale qui se caractérise par un déficit de communication et interaction sociale ainsi que par des comportements répétitifs et intérêts restreints. Son diagnostic a considérablement augmenté ces dernières décennies, principalement à cause de la plus grande reconnaissance de la maladie et la fin de plusieurs préjugés. C'est pourquoi les chercheurs en neuro-développement se concentrent sur l'autisme pour encore mieux connaître ses mécanismes. Pour ce faire, ils utilisent des modèles de souris dans une grande quantité d'études, pour éviter les études avec les humains qui pourraient être barrés à cause des contraintes éthiques.
Dans le cadre de ce projet, nous travaillons dans le but de faire la modélisation du comportement des souris par des approches de vision par ordinateur et d'apprentissage profond. L'idée, c'est de retrouver des séquences de comportement qui distinguent une souris contrôle d'une souris pathogénique à l'aide des algorithmes de CV/DL. Pour cela, nous nous servirons d'un outil appelé LMT, qui fait l'enregistrement des souris et génère la base de données que nous utiliserons. Cet outil, malgré sa puissance, laisse certaines difficultés liées à un certain manque de robustesse dans l'identification des souris. Nous avons donc constitué une chaîne de prétraitement pour combler au mieux ces faiblesses. Aussi, nous avançons sur des recherches pour suivre et prédire l'action d'une souris sans utiliser ledit système. Cela nous sera utile à modéliser la gestation et les premiers jours de vie des souris.
Cette présentation abordera alors une brève contextualisation sur l'autisme et la recherche animale, ensuite, la présentation de la problématique sur laquelle nous travaillons. Une revue de l'état de l'art sera faite dans les principaux champs croisés par cette recherche. Je montrerai aussi l'outil LMT ainsi que la chaîne de prétraitement constitué, bien comme les progrès faits jusqu'à présent ainsi que les perspectives pour la suite du projet.

Seminaire : Demi-journée du Pole Calcul : Algorithmique et Structures Discrètes

28/03/2024 à 09h30

Demi-journée du Pole Calcul (2 seminaires)

Speaker: Pablo Arrighi (LMF, Université Paris-Saclay)
Title: Past, future, what's the difference?
Abstract: The laws of Physics are time-reversible, making no qualitative distinction between the past and the future---yet we can only go towards the future. This apparent contradiction is known as the `arrow of time problem'. Its current resolution states that the future is the direction of increasing entropy. But entropy can only increase towards the future if it was low in the past, and past low entropy is a very strong assumption to make, because low entropy states are rather improbable, non-generic. Recent works from the Physics literature suggest, however, we may do away with this so-called `past hypothesis', in the presence of reversible dynamical laws featuring expansion. We prove that this is the case, for a synchronous graph rewriting-based toy model. It consists in graphs upon which particles circulate and interact according to local reversible rules. Some rules locally shrink or expand the graph. Generic states always expand; entropy always increases---thereby providing a local explanation for the arrow of time. This discrete setting allows us to deploy the full rigour of theoretical Computer Science proof techniques.

Speaker: Pierre Ohlmann (MoVe, LIS)
Title: FO-model checking over monadically stable graphs classes
Abstract: in this talk, we will survey recent results (mostly not by me) about efficient model-checking of first-order logic sentences over graphs. We will aim to give a general overview of this very active field, and discuss the different ingredients that come into play. Time allowing, we will go into more details about one of these ingredients: the Flipper game for characterizing monadically stable classes.

Seminaire : Séminaire ACRO : Caroline Brosse (Inria, Université Côte d’Azur)

25/03/2024 à 10h00

Caroline Brosse (Inria, Université Côte d’Azur) Title: Polynomial delay algorithm for minimal chordal completions 25/03/2024 10h00, salle REU 04.05 (LIS Luminy) Motivated by the problem of enumerating all tree decompositions of a graph, we consider in this article the problem of listing all the minimal chordal completions of a graph. In PODS 2017 Carmeli et al. proved that all minimal chordal completions or equivalently all proper tree decompositions of a graph can be listed in incremental polynomial time using exponential space. The total running time of their algorithm is quadratic in the number of solutions and the existence of an algorithm whose complexity depends only linearly on the number of solutions remained open. We close this question by providing a polynomial delay algorithm to solve this problem which, moreover, uses polynomial space. Our algorithm relies on Proximity Search, a framework recently introduced by Conte et al. (STOC 2019) which has been shown powerful to obtain polynomial delay algorithms, but generally requires exponential space. In order to obtain a polynomial space algorithm for our problem, we introduce a new general method called canonical path reconstruction to design polynomial delay and polynomial space algorithms based on proximity search.

Seminaire : Séminaire CANA : Bert Lindenhovius

19/03/2024 à 14h00

Où : via zoom et en salle 04.05, bât TPR2, Luminy

Titre : A noncommutative framework for quantum information theory and quantum programming

Résumé : Many quantum phenomena have classical counterparts, and are modeled by mathematical structures that are noncommutative generalizations of the mathematical structures that model these classical counterparts. Quantization is the process of finding such as noncommutative generalization, and relies heavily on the theory of operator algebras, i.e., algebras of continuous linear maps on a fixed Hilbert space. Operator algebras generalize complex-valued matrix algebras, and can be used to describe quantum systems beyond finite-level systems. We will discuss a relatively new quantization method, called discrete quantization, based on the concepts of quantum sets and quantum relations between them. Quantum sets are essentially (possibly infinite) sums of matrix algebras and form a class of operator algebras that generalize sets, whereas quantum relations are a kind of morphism between quantum sets generalizing binary relations between ordinary sets. We discuss how several structures relevant for quantum information theory such as the quantum hamming distance and quantum graphs can be understood via discrete quantization. Moreover, we will discuss quantum cpos, a noncommutative generalization of omega-complete partial orders (cpos), obtained via discrete quantization. Ordinary cpos are the main objects of study in domain theory, which is the underlying mathematical theory for the construction of mathematical models of programming languages in a structured way. In a similar way, we discuss how quantum cpos can be used for the construction of mathematical models of quantum programming languages in a structured way.

Seminaire : Séminaire CANA : Nicolas Blanco (CEA)

19/03/2024 à 10h00

Où : via zoom et en salle 04.05, bât TPR2, Luminy

Titre : A categorical framework to study logical properties of systems and processes

Résumé : Categorical quantum mechanics and applied category theory are fields that study systems and processes by abstracting the main structures and properties of their models. A focus is put on compositionality: how to compose processes together and to describe complex systems from their subsystems. An important structure studied in these fields is given by compact closed categories. They correspond to models of one-to-one processes that can be sequentially composed (a category), where systems and processes can be composed in parallel (a tensor/monoidal product) and each system has a dual system that reverse the flow of information. Processes with many inputs and outputs can then be modelled as processes between the tensor product of the inputs and the tensor product of the outputs. Linear logic is a substructural logic where the information in a proof cannot be duplicated nor erased. That is, every hypothesis has to be used exactly once. It is closely connected to linear type theory through a Curry-Howard correspondence. Through categorical semantics one can study the structures and properties of its models. An important structure in this field is given by *-autonomous categories. These correspond to models of one-to-one proofs that can be sequentially composed (a category), where logical propositions can be composed in two ways, the conjunction and disjunction (two monoidal products, the tensor and the par), and where each proposition can be negated (a duality). Proofs with many hypotheses and many conclusions can then be modelled as proofs from the conjunction of the hypotheses to the disjunction of the conclusions. It turns out that a compact closed category is exactly a *-autonomous category where the two monoidal products coincide, i.e. the conjunction and disjunction have the same interpretation. This lead to a line of research exploring the connection between linear logic and quantum mechanics, amongst others. For example, Aleks Kissinger and Sander Uijlen showed that starting with a compact closed category modelling systems and processes, one can studied their causal structure logically by organising the causal systems and processes into a *-autonomous category. In this talk, I will consider these connections by adopting a slightly different perspective. Instead of considering one-to-one processes or proofs, I will take many-to-many ones as a primitive, in a structure called a polycategory. The monoidal products (and the duals) will then be recovered through a universal property akin to the one of the tensor products of vector spaces. This will determine the interpretation of the composition of systems or logical propositions uniquely, up-to unique isomorphism, instead of having it provided as extra data. Furthermore, it will make apparent another defining distinction between the compact closed and the *-autonomous models: in the latter the sequential composition is done along one specific object while in the former two processes can be composed along multiple systems. In particular compact closed categories allow for feedback and loops while *-autonomous categories don't. I will then introduce bifibred polycategories explaining how they can be used to model the emergence of a logical framework structuring systems equipped with specific conditions. They are in part inspired by Hoare logic, a framework used in computer science to reason about and verify properties of programs. As an example, I will consider the case of finite dimensional Banach spaces and contractive polylinear maps. Finite dimensional vector spaces and polylinear maps will provide a model of systems and processes while the norms will be used to express conditions on states of the systems via (sub-)unitality. Another example is given by the aforementioned construction of causal structures. If time permits, I will present some research directions I am considering to extend this framework.

Seminaire : Séminaire GMOD : Quentin Wendling

15/03/2024 à 10h00

Titre : Couplage géométrie/mécanique pour l'animation d'objets détaillés Résumé : Mes travaux se concentre sur la construction d'une reproduction numérique précise du comportement d'objets déformables détaillés, en relevant le défi d'équilibrer les exigences visuelles avec les performances en temps réel. Pour ce faire, j'ai introduit le concept de vues adaptatives, une représentation multirésolution unique pour tous les aspects de l'animation, du calcul physique au rendu graphique. En utilisant des cartes combinatoires multirésolutions, notre approche utilise des résolutions grossières pour les degrés de liberté de la simulation et des résolutions fines pour les détails géométriques. Les vues adaptatives permettent une distribution flexible des degrés de liberté, améliorant la précision dans les zones déformées sans sacrifier les performances. Nous avons appliqué avec succès ce concept à deux méthodes de simulation mécanique, Shape Matching basé sur la physique et Smoothed Particle Hydrodynamics (SPH), en les adaptant à notre cadre adaptatif. Nos critères d'adaptation incluent des interactions objet-simulation et des propriétés physiques telles que le stress. De plus, notre approche gère efficacement les coupes d'objet en utilisant des méthodes de découpe le long des faces existantes. Les résultats de nos benchmarks démontrent une amélioration significative des performances, avec une efficacité adaptative plus de 10 fois supérieure à la simulation sur maillage fin, tout en maintenant une qualité visuelle similaire. Cette approche offre une solution innovante pour la représentation et la simulation d'objets déformables hautement détaillés, avec des applications potentielles dans divers domaines de l'informatique graphique et de la simulation mécanique. Plus d'informations : https://g-mod.lis-lab.fr/presentation-quentin-wendling-15-03-2024/

Seminaire : Séminaire CANA : Aidan Chatwin-Davies

12/03/2024 à 14h00

Où : online & salle 04.05, bât TPR2, Luminy

Titre : Quantum Information Processing with Gravitating Systems and More

Résumé : Quantum information theory quantifies the remarkable and surprising ways that quantum systems can be used to compute. Connecting the abstract theory to concrete physical systems often gives insight into a system’s physics; conversely, physical intuition can often inspire new ideas for information theory itself. This perspective has been particularly fruitful in quantum gravity, for which the essential question is to understand how gravitating systems store and process information. In this talk, we will explore how these two-way connections play out, in particular among quantum algorithms, quantum error correction, and gravitational holography. Time permitting, I will further discuss recent work that connects quantum error correction with areas of physics beyond gravity.

Seminaire : Séminaire CANA : Djamel Eddine Amir

28/02/2024 à 14h00

Où : salle 04.05, bât TPR2, Luminy

Titre : Computable Aspects of Topological Spaces

Résumé : The topological properties of a set have a strong impact on its computability properties. A striking illustration of this idea is given by spheres and closed manifolds : if a set X is homeomorphic to a sphere or a closed manifold, then any algorithm that semicomputes X in some sense can be converted into an algorithm that fully computes X. In other words, the topological properties of X enable one to derive full information about X from partial information about X. In that case, we say that X has computable type. Those results have been obtained by Miller and Iljazović and others in the recent years. We give a characterization of finite simplicial complexes having computable type using a local property of stars of vertices. Moreover, the reduction to homology implies that the computable type property is decidable, for finite simplicial complexes of dimension at most 4. We argue that the stronger, relativized version of computable type, is better behaved. Consequently, we obtain characterizations of strong computable type, related to the descriptive complexity of topological invariants. This leads us to investigate the expressive power of low complexity invariants in the Borel hierarchy and their ability to differentiate between spaces. Notably, we show that they are sufficient for distinguishing finite topological graphs.

Seminaire : Séminaire CANA : Niall Murphy

27/02/2024 à 14h00

Où : online & salle 04.05, bât TPR2, Luminy

Titre : An implementable quantum algorithm for approximating geometric entanglement for pure states

Résumé : Entanglement is a fundamental property of a quantum state that is a crucial differentiator between classical computation and quantum. Naturally, given its essential relevance to quantum algorithms and computation, there are many definitions of entanglement each with many classical methods to compute or approximate these values. Surprisingly, hardly any of these algorithms can be run on near term quantum hardware. In this work we introduce a new quantum algorithm to compute the geometric entanglement of multi-qubit pure states.

Seminaire : Séminaire I&M - Jules collenne

23/02/2024 à 14h00

Titre :Aide au diagnostic du mélanome : approche par apprentissage de similarités
Lieu : Luminy, TPR2 salle de réunion 04.03.
Résumé :
Le mélanome est un cancer de la peau très grave, dont l'incidence ne cesse d'augmenter. Pour réduire son impact, d'importants efforts sont déployés afin de surveiller cette maladie au sein de la population. Ces efforts ont donné naissance à d'importantes bases de données annotées, où chaque image est classifiée comme étant un cancer ou une lésion bénigne. Ces bases de données peuvent être utilisées pour entraîner des modèles d'apprentissage automatique. Les modèles précédents se basaient exclusivement sur l'utilisation d'images uniques pour détecter le mélanome. Cependant, les approches permettant la comparaison des différentes lésions d'un même patient semblent très prometteuses pour améliorer la précision des diagnostics et l'interprétabilité des résultats. En particulier, les récentes avancées en apprentissage automatique, telles que les modèles à mécanismes d'attention, les Transformers, et les modèles d'apprentissage de représentations visuelles auto-supervisés, permettent de générer et de comparer de manière efficace les embeddings issus des images de lésions cutanées.

Seminaire : Séminaire CANA : Léo Gayral

20/02/2024 à 14h00

Où : Salle 04.05, bât TPR2, Luminy

Titre : Uniformly Chaotic Finite-Range Lattice Models

Résumé : L’étude de modèles de physique statistique permet aux mathématiques d’offrir un autre regard sur des phénomènes observables empiriquement. Un point d’intérêt est notamment le comportement de ces modèles lorsque la température tend vers 0, analogue à l’émergence de structures cristallines complexes dans des matériaux. En 2010, Chazottes et Hochman ont exhibé un potentiel tridimensionnel à interactions locales, pour lequel le système induit est chaotique, i.e. aucune trajectoire du système ne converge à température zéro. Dans cet exposé, on va s’intéresser plus en détail à la construction d’un modèle similairement chaotique, et permettant en outre un contrôle assez fin sur l’ensemble des valeurs d’adhérence des trajectoires. Pour ce faire, on introduira notamment une famille de pavages apériodiques, dont les propriétés combinatoires permettent de contrôler l’entropie, d’encoder des machines de Turing, de « simuler » des mesures de probabilité…

Seminaire : Séminaire GMOD : Guillaume Coiffier

16/02/2024 à 10h00

Titre : Algorithmes de Paramétrisation Globale pour Maillages Quadrangulés Résumé : Nous nous intéressons à l’amélioration des différentes étapes du pipeline de génération de maillages quadrangulaires. En nous appuyant sur des notions de géométrie différentielle, nous proposons des formulations du problème évitant les écueils de l’approche actuelle. Premièrement, nous abandonnons la résolution de problèmes en nombre entier pour certaines étapes [...] Deuxièmement, nous fusionnons certaines étapes du pipeline en une seule optimisation déterminant en un seul coup les degrés de liberté correspondants. [...] Plus d'informations : https://g-mod.lis-lab.fr/presentation-guillaume-coiffier-16-02-2024/

Conference : Exploiting Knowledge Graphs in LLM-based Applications

13/02/2024 à 10h00

Les Graphes de Connaissance (GC), Knowledge Graphs en anglais, sont des structures de données puissantes qui représentent des connaissances sous forme de graphes orientés. Ils permettent de modéliser les relations entre les entités et les concepts dans un domaine spécifique, facilitant ainsi la compréhension et l'exploitation des informations. Ce séminaire explorera les aspects fondamentaux, l'applicabilité et les avancées récentes dans le domaine des GC. Nous verrons une définition approfondie des GC, en mettant l'accent sur leur rôle dans la représentation et l'organisation des connaissances. Nous discuterons de l'applicabilité des GC dans divers domaines, tels que l'ingénierie des connaissances, le web sémantique et l'extraction d'information. De plus, nous discuterons de la synergie entre les GCs et les récents Grands Modèle de Langage (LLM). Découvrez comment ces structures de données peuvent transformer la façon dont nous représentons, organisons et exploitons les connaissances.

Seminaire : Séminaire GMOD : Nicolas Lutz

09/02/2024 à 10h00

Titre : Processus stochastiques pour la génération de textures et de géométrie Résumé : La synthèse de textures en temps réel et par l’exemple est utilisée dans le rendu pour générer de la variété visuelle sur de larges surfaces texturées. Nous présentons nos travaux les plus récents en synthèse de textures, qui s’appuient sur le modèle théorique de l’exploitation de champs stochastiques spécifiques. Nous montrons que ce modèle théorique permet également de synthétiser les valeurs d’autres fonctions continues, avec comme premiers résultats nos travaux pour la synthèse de la géométrie et de l’apparence d’un océan animé en temps réel. Plus d'informations : https://g-mod.lis-lab.fr/presentation-nicolas-luz-09-02-2024/

Seminaire : Séminaire CANA : Daria Pchelina (LIP, ENS Lyon)

06/02/2024 à 14h00

Où : Salle 04.05, bât TPR2, Luminy

Titre : Density of disc and sphere packings

Résumé : How to stack an infinite number of oranges to maximize the proportion of the covered space? Kepler conjectured that the ``cannonball'' packing is an optimal way to do it. This conjecture took almost 400 years to prove, and the proof of Hales and Ferguson consists of 6 papers and tens of thousands of lines of computer code. Given an infinite number of coins of 3 fixed radii, how to place them on an infinite table to maximize the proportion of the covered surface? Triangulated disc packings are those where each "hole" is bounded by three pairwise tangent discs. Connelly conjectured that for the sets of disc radii where triangulated packings exist, one of them maximizes the proportion of the covered surface; this holds for unary and binary disc packings. In this talk, we will discuss various techniques used in the proof of the Kepler conjecture and other important results in the domain of disc and sphere packings. They allow us to prove the statement of the Connelly conjecture for 31 triangulated triplets of disc radii and disprove it for 45 other triplets. Besides that, we obtain tight bounds on the local density of simplicial cells in 2-sphere packings. Besides that, we will talk about some open questions of the domain in connection with tilings and computability.

Seminaire : Séminaire ACRO : Oscar Defrain (05 février, 10h)

05/02/2024 à 10h00

Séminaire ACRO : Oscar Defrain (05 février, 10h) Titre : Énumération Algorithmique IV. Supergraph method. Résumé : Cet exposé est le quatrième d’une série d’exposés sur le thème de l’énumération algorithmique où sont 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 à une technique d’énumération généralement appelée « supergraph method » qui repose sur le parcours d’un graphe des solutions bien choisi. On s’intéressera en particulier à l’énumération des sous-graphes vérifiant une propriété héréditaire, des arbres couvrant d’un graphe, ou encore à l’énumération des bases d’un matroid. https://acro.lis-lab.fr/seminars

Seminaire : Séminaire GMOD : Sylvain Gerbaud

02/02/2024 à 10h00

Titre : Reconstructions 3D tissulaires basées sur le métabolisme sous-jacent exploré en spectroscopie par résonance magnétique Résumé : Nous proposons un modèle 3D continu dédié à l’étude du cerveau , qui centralise les données anatomiques et toutes les informations issues du contexte d’application. Nous décrivons une nouvelle méthode de reconstruction pour modéliser les tissus cérébraux, enrichi par des informations de sémantique et topologiques. Plus d'informations : https://g-mod.lis-lab.fr/presentation-sylvain-gerbaud-02-02-2024/

Seminaire : Demi-journée du Pole-Calcul : Géométrie et topologie du Calcul

01/02/2024 à 09h30

Demi-journée du Pole Calcul (3 seminaires)

Speaker : Bruno Lévy (INRIA, U. Paris-Saclay)
Title: A Lagrangian method for fluids with free boundaries
Abstract: In this presentation, I'll describe a numerical simulation method for free-surface fluids. I will start by giving an intuitive understanding of the physical phenomena involved in fluid dynamics, pressure, viscosity and surface tension. Then I will detail the numerical simulation method, based on the Gallouet-Mérigot numerical scheme, that describes the fluid as a set of cells, that can deform, but that keep a constant volume, and that follow the motion of the fluid (Lagrangian method). The constant volume constraint takes the form of a partial semi-discrete optimal transport. I will present the geometric and numerical aspects of this optimal transport problem. The volume conservation constraint takes the form of a partial semi-discrete optimal transport problem. The solution of this transport problem determines the nature of the cells, that correspond to the intersection between Laguerre cells and balls.

Speaker : Guilherme Dias da Fonseca (ACRO)
Title: Shadoks Approach to Convex Covering and Other CG:SHOP Challenges
Abstract: The CG:SHOP Challenge is a geometric optimization challenge organized annually as part of the prestigious SoCG conference. A different problem is proposed each year and the Shadoks team obtained several good results in the last 6 years. We describe these 6 problems, general algorithmic ideas, and strategy used in CG:SHOP 2023. The CG:SHOP 2023 challenge consisted of 206 instances, each being a polygon with holes. The goal was to cover each instance polygon by a small number of convex polygons inside the instance polygon (fewer polygons mean a better score). Our strategy was the following. We find a big collection of large (often maximal) convex polygons inside the instance polygon and then solve several set cover problems to find a small subset of the collection that covers the whole polygon. ( Paper: https://arxiv.org/abs/2303.07696 )

Speaker : Alexandra Bac (GMOD)
Title: Combinatorial duality
Abstract : Alexander duality establishes the relation between the homology of an object and the cohomology of its complement in a sphere. For instance, if X is a subset of the 2-dimensional sphere S2, then each hole of X corresponds to a connected component of S2 \ X, and by symmetry, each hole of S2 \ X corresponds to a connected component of X. In this work we present a new combinatorial and constructive proof of Alexander duality that provides an explicit isomorphism. The proof shows how to compute this isomorphism using a combinatorial tool called homological colorings. It also provides a one-to-one map between the holes of the object and the holes of its complement, which we use for representing the holes of an object embedded in R3.

Seminaire : Séminaire CANA : Hippolyte Dourdent (ICFO)

30/01/2024 à 14h00

Où : Visio Zoom diffusée en salle 04.05, bât TPR2, Luminy

Titre : All You Need to Know about the Quantum Switch

Résumé : While the standard formulation of quantum theory assumes a fixed background causal structure, the process matrix formalism allows to relax this assumption and explore the possibility of processes with indefinite causal orders. For example, one may imagine a quantum circuit in which the order between Alice and Bob’s operations on a target system is coherently controlled by another quantum system, such that their operations are in a superposition of causal orders. This so called "quantum switch" has already been shown to offer advantages in various information processing tasks. In this review, I will introduce the notion of causal nonseparability – formalizing the notion of indefinite causal orders – and its various certifications in a quantum switch. I will then give examples of applications for quantum information and present a crucial tool allowing to assess whether such advantages genuinely come from indefinite causal orders or not.

Conference : Sémnaire MoVe anvec Chana Weil-Kennedy

26/01/2024 à 10h30

Qui ? Chana Weil-Kennedy Quand ? Vendredi 26/01 à 10h30 Où ? 4.05 TPR2 Luminy Quoi ? Title: Parameterized Analysis of Distributed Systems Mais encore ? My future research project focuses on parameterized verification of distributed systems, where the parameter is often the number of agents present in the system. During my thesis with Javier Esparza in Munich, I studied this kind of problem for subclasses of Petri nets with application to population protocols (a distributed computing model), but also for systems communicating by broadcast or by shared register. Currently in my postdoc I am continuing the study of these systems with "simple" modes of communication, and I'm also starting to look at language inclusion problems. In the future, I want to continue to analyze distributed systems for which the parameterized problems are not immediately undecidable, broadening the range of formal method techniques used. I will concentrate on distributed systems that are decentralized, symmetric (agent identities are interchangeable), and with local interactions.

Seminaire : Séminaire CANA : Martin Plávala

23/01/2024 à 14h00

Où : en ligne et salle 04.05, bât TPR2, Luminy

Titre : Optimization in quantum information: from foundations to applications

Résumé : This talks investigates a class of common optimization problems in quantum information, semi-device-independent certification of Schmidt number of quantum states will be used as a specific example. Solutions to such problems will be presented as a byproduct of investigating the mathematical/foundational question whether entanglement exists in all non-classical operational theories. This problem was already considered as a mathematical problem by George Barker in the 70’ in the context of ordered vector spaces. As a consequence of this result, the need for mathematical tools to detect entanglement in all operational theories arises, we address this issue by presenting a generalization of the Doherty-Parrilo-Spedalieri (DPS) hierarchy to operational theories. Finally we discuss the unexpected applications of these results to solve initial problem of semi-device independent certification of Schmidt number of quantum states, for which we derive tight SDP hierarchy.

Seminaire : Séminaire ACRO : Yann Strozecki

22/01/2024 à 13h00

Yann Strozecki (DAVID, Université de Versailles Saint-Quentin) Title: Geometric Amortization of Enumeration Algorithms 22/01/2024 13h00, salle REU 04.05 (LIS Luminy) We introduce the technique of geometric amortization for enumeration algorithms. This technique can be used to make the delay of enumeration algorithms more regular without much overhead on the space it uses. More precisely, we are interested in enumeration algorithms having incremental linear delay, that is, algorithms enumerating a set A of size K such that for every t≤K, it outputs at least t solutions in time O(tp), where p is the incremental delay of the algorithm. While it is folklore that one can transform such an algorithm into an algorithm with delay O(p), the naive transformation may blow the space exponentially. We show that, using geometric amortization, such an algorithm can be transformed into an algorithm with delay O(plogK) and O(slogK) space, where s is the space used by the original algorithm. We apply geometric amortization to show that one can trade the delay of flashlight search algorithms for their average delay modulo a factor of O(logK). We illustrate how this tradeoff may be advantageous for the enumeration of solutions of DNF formulas.

Seminaire : Séminaire CANA : Victor Lutfalla

16/01/2024 à 14h00

Où : Salle 04.05, bât TPR2, Luminy

Titre : Bootstrap percolation on Penrose tilings

Résumé : Penrose tilings are non-periodic tilings of the plane by two rhombuses up to isometry. Here we study dynamic percolation: a contamination process on Penrose tilings starting from a random initial configuration. Given a Penrose tiling we put a state 0 or 1 on each tile. On these configurations we run the Boostrap percolation cellular automaton: state 1 is stable and a 0 cell becomes 1 if it has (at least) two 1 neighbors. We say that a configuration percolates when its limit configuration is 1-uniform, i.e., when running the Bootstrap percolation cellular automaton on the configuration, every tile eventually gets contaminated. Denote B the set of configuration that percolate. We prove that for any Bernoulli measure μ (of positive parameter d) we have μ(B)=1. In other words, for any positive parameter d, if we pick an initial configuration c at random on a Penrose tiling following a Bernoulli distribution of parameter d the probability that c percolates is 1.

Seminaire : Séminaire DALGO : Francois-Xavier Dupé

16/01/2024 à 10h30

Où : Salle 04.05, bât TPR2, Luminy

Titre : Introduction aux méthodes et problématiques d’optimisations rencontrées en apprentissage automatique

Résumé : Cet exposé présentera une partie des problématiques rencontrées en apprentissage automatique. Chaque problématique implique une modélisation conduisant à un problème d’optimisation souvent simplifié via des hypothèses assez fortes. L’augmentation de la taille des modèles (nombre de paramètres) et de la quantité de données demande l’utilisation d’algorithmes de résolution capable de passer à l’échelle, d’où l’utilisation de méthodes stochastiques et de questions de distributions des calculs. Autour de ces méthodes d’autres questions se posent comme la borne en erreur de généralisation ou la correction des biais connus ou non. L’exposé sera l’occasion de présenter ces questions et leurs implications.

Seminaire : Séminaire CANA : Simon Milz

09/01/2024 à 14h00

Où : Salle 04.05, bât TPR2, Luminy

Titre : (Some) consequences of invasiveness in quantum mechanics

Résumé : No physical system is every truly isolated from its surrounding environment. This particularly holds in quantum mechanics and leads to complex memory effects in the multi-time statistics of (quantum) stochastic processes. In contrast to the standard paradigm of classical stochastic processes, measurements in quantum mechanics are generally invasive, i.e., they change the state of the probed system, leading to a multitude of novel phenomena. In particular, invasiveness a priori stands in the way of a consistent quantum generalization of basic concepts used in the description of classical stochastic processes. In my talk, I will discuss how fundamental tenets of the theory of classical stochastic processes, like the Kolmogorov extension theorem (defining the notion of a stochastic process) and Markov order (defining the length/strength of memory) can meaningfully be recovered in quantum mechanics. Going beyond these generalizations of classical concepts, quantum memory possesses a much richer structure than its classical counterpart and affords for memory effects that do not exist in the classical world. I will discuss the instrument dependence of memory effects in quantum mechanics, as well as the possibility of hidden quantum memory, i.e., the existence of quantum processes with Markovian statistics that nonetheless fundamentally require memory for their implementation. Finally, invasiveness, one of the main 'culprits' for the complexity of quantum memory effects could, in principle, also be implemented in classical physics, putting in question the 'quantumness' of the aforementioned phenomena. By introducing the concept of 'genuinely quantum processes', I will however argue that, while an active choice in classical physics, invasiveness is a fundamentally unavoidable trait in quantum processes.

Seminaire : Séminaire ACRO : Oscar Defrain (08 janvier, 10h)

08/01/2024 à 10h00

Salle REU 04.05 Titre : Sparse graphs without long induced paths Résumé court : Graphs of bounded degeneracy are known to contain induced paths of order Ω(log log n) when they contain a path of order n, as proved by Nešetřil and Ossona de Mendez (2012). In 2016 Esperet, Lemoine, and Maffray conjectured that this bound could be improved to Ω((log n)^c) for some constant c>0 depending on the degeneracy. We disprove this conjecture by constructing, for arbitrarily large values of n, a graph that is 2-degenerate, has a path of order n, and where all induced paths have order O((log log n)^2).

Conference : Séminaire CANA : Célia Biane Fourati

12/12/2023 à 00h00

Où : Salle 04.05, bât TPR2, Luminy

Titre: 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, Luminy

Titre : 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, Luminy

Titre : 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, Luminy

Titre : 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, Luminy

Titre: 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, Luminy

Titre: 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 Obstacles

Ré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, Luminy

Titre: 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, France

Seminaire : 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/seminars

Seminaire : 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 deconvolution
Lieu : 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. Square zoo of coverings

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

Seminaire : 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 Toulon

Seminaire : 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.37
Zoom : 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 Garde

Seminaire : 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 Togni

Seminaire : 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équences

Seminaire : 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 Marseille

Seminaire : 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 Meddouri
Lien 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 Calvet
Lien 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 Galanov
Salle: 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 Grente
Salle: 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.37
Titre: 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 Gangloff
Titre : 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 Novo
Title: 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 Akmal
Title: 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 Carette
Salle : 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 : FRUMAM

Orateurs :
- 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.05
Titre : 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.org

Conference : 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 2021

Encore 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.fr

Seminaire : 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 Constraints
Abstract : 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 9740

WorkShop : 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 equations
Abstract : 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.fr

Titre : 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 Durbec
Titre : 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.fr

Titre : 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 Perrotin
Titre : 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 visio

Seminaire : 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 zoom

Seminaire : 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.fr

Titre : 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 zoom

Seminaire : 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, Luminy

Seminaire : 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), Luminy

Seminaire : 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.fr

Les 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), Luminy

Seminaire : 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

Seminaire : 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), Luminy

Seminaire : 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), Luminy

Seminaire : 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), Luminy

Seminaire : 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ôme

Seminaire : Séminaire du Pôle ACS : Michel Zasadzinski

18/12/2019 à 14h00

Salle des commissions, St. Jérôme

Seminaire : 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 commissions
Yacine 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

Le séminaire pourra être suivi en visioconférence depuis la salle X133 du bâtiment X à Toulon.
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 Pous

Rencontre : 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/g8uU4SknutQJh2hD7

Seminaire : 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 fil
Orateurs: 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, à Luminy

Seminaire : 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.html

Workshop 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

Organizers

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.