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

Workshop on Machine Learning and Quantum Computation

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.

    Soutenance de Thèse : Soutenance de thèse : "Recommandation automatique, temps réel, et adaptative d'emojis" - G. Guibon, St Jérôme


    24/05/2019 à 14h00

    Depuis leur apparition en 1999, les emojis ont une popularité grandissante dans les systèmes de communication. Ces petites images pouvant représenter une idée, un concept ou une émotion, se retrouvent disponibles aux utilisateurs dans de nombreux contextes logiciels : messagerie instantanée, courriel, forums et autres réseaux sociaux en tout genre. Leur usage, en hausse constante, a entraîné l'apparition récurrente de nouveaux emojis, allant jusqu'à 2 789 emojis standardisés en fin d'année 2018. Le parcours de bibliothèques d'emojis ou l'utilisation de moteur de recherche intégré n'est plus suffisant pour permettre à l'utilisateur de maximiser leur utilisation ; une recommandation d'emojis adaptée est nécessaire. Pour cela nous présentons nous travaux de recherche axés sur le thème de la recommandation d'emojis. Ces travaux ont pour objectifs de créer un système de recommandation automatique d'emojis adapté à un contexte conversationnel informel et privé. Ce système doit améliorer l'expérience utilisateur et la qualité de la communication, en plus de pouvoir prendre en compte d'éventuels nouveaux emojis créés. Dans le cadre de cette thèse, nous contribuons tout d'abord en montrant les limites d'usage réel d'une prédiction d'emojis ainsi que la nécessité de prédire des notions plus générales. Nous vérifions également si l'usage réel des emojis représentant une expression faciale d'émotion correspond à l'existant théorique. Enfin, nous abordons les pistes d'évaluation d'un tel système par l'insuffisance des métriques, et l'importance d'une interface utilisateur dédiée. Pour ce faire, nous utilisons une approche orientée apprentissage automatique à la fois supervisée et non supervisée, ainsi que la conception de modèles de langues ou, plus précisément, de plongements lexicaux. Plusieurs composantes de ce travail ont donné lieu à des publications nationales et internationales, dont le prix du meilleur logiciel reproductible, ainsi que celui du meilleur poster pour la catégorie des médias sociaux. La soutenance sera présentée devant un jury composé de : Chloé CLAVEL, rapportrice - Télécom ParisTech Horacio SAGGION, rapporteur - Universitat Pompeu Fabra Béatrice DAILLE, examinatrice - LS2N-CNRS, Université de Nantes Frédéric LANDRAGIN, examinateur - LaTTiCe-CNRS, ENS Pierre LISON, examinateur - Norsk Regnesentral, Norwegian Computing Center Patrice BELLOT, directeur - LIS-CNRS, Aix-Marseille Université Magalie OCHS, co-directrice - LIS-CNRS, Aix-Marseille Université

    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 con gurations. Thus, our algorithms achieve close to optimal idle time. Further, we show a clear separation in terms of idle time, for agents that have prior knowledge of the dynamic networks compared to agents that do not have such knowledge. This paper provides the first known results for collaborative patrolling on dynamic graphs. (Note: Joint work with Giuseppe. A. Diluna and Leszek A. Gasieniec.) Salle de réunion du LIF, Luminy (Préfabriqué)

    Seminaire : Séminaire Analyse et Contrôle des Systèmes


    25/04/2019 à 14h00

    Séminaire de Angelo Alessandri (DIME, Università di Genova) (Toulon)

    Seminaire : Séminaire CaNa : 02/04, 15h : Pedro Balbi de Oliveira


    02/04/2019 à 15h00

    Le séminaire de Pedro Balbi de Oliveira se déroulera le 2 avril 2019 en salle de réunion du BP5 à luminy.

    Titre : "Could density determination be solved with one-dimensional binary cellular automata with asynchronous update?"

    Abstract: This title reflects the question that will start to be addressed during my visit to LIS. In the talk I will discuss the background about it, and give some idea about how the problem can be tackled. In its original formulation, density determination refers to the problem of deciding, by means of a one-dimensional cellular automaton rule, which is the most frequent bit in a cyclic binary configuration. This is one of the most widely studied benchmark decision problems in the cellular automata literature. In spite of various positive and negative results already known on the problem, in its various formulations, the possibility of solving it with a rule being updated in a deterministic asynchronous fashion is still open.


    Seminaire : Séminaire Analyse et Contrôle des Systèmes


    28/03/2019 à 14h00

    Séminaire de Hassan Hammouri (LAGEP, Lyon) St. Jérôme

    Seminaire : Séminaire Analyse et Contrôle des Systèmes


    21/03/2019 à 14h00

    Séminaire de Frédéric Mazenc (L2S)

    Seminaire : [1ère demi-journée Pole Calcul LIS] “Logique et Méthodes formels”


    21/03/2019 à 09h30

    Dans le cadre du deuxième cycle des demi-journées du Pole Calcul du LIS, la prochaine sera autour du thème “Logique et Méthodes formels”, organisée le jour *21 Mars 9h30 à 12h30 (Luminy) dans l’Amphi 12 de Luminy.

    Les demi-journées seront aussi enregistrés et on les rendra publique les vidéos sur une page dédiée ou sur une chaine youtube (lien à venir).

    Les trois intervenants confirmés sont Damien Busatto-Gaston (LIS), Belaid Benhamou (LIS), Jean-Francois Raskin (ULB)

    —————————————————————————————

    Première demi-journée (Logique et Méthodes formelles) 21 Mars

    (45min each + 10 mins questions + 15 min coffe break)

    9h30 -> 10h15 — Damien Busatto-Gaston (PhD) , LIS

    Titre : Synthesizing robust controllers for Büchi conditions in timed systems.

    Abstract :

    We solve the robust controller synthesis problem in timed automata with Büchi acceptance conditions. The goal of the controller is to play according to an accepting lasso of the automaton, while resisting to timing perturbations chosen by a competing environment. The talk will introduce classical notions for studying timed automata (regions, zones, constraint graphs) and explain how these can be extended to compute strategies that are resilient to arbitrarily small perturbations. We will also introduce a way to compute the largest perturbation allowed by a given controller. Our techniques are illustrated by the regulation of a train network.

    10h25 -> 11h10 — Belaid Benhamou (MCF), LIS

    Titre : Programmation logique au sens ASP (Answer Set Programming) : une nouvelle sémantique capturant et étendant celle des modèles stables.

    Abstract :

    Plusieurs travaux ont été faits pour définir des sémantiques pour les programmes logiques normaux. La plupart de ces sémantiques sont en fait des sémantiques de points fixes. L’idée principale est le calcul de modèles canoniques du programme logique considéré, appelés modèles stables (Gelfond et al. 1988). Dans cette exposé, nous décrivons une nouvelle sémantique pour les programmes logiques normaux. Cette dernière est basée sur une notion d’extensions de formules propositionnelles classiques. Un programme logique est alors codé par un ensemble de clauses de Horn propositionnelles. On prouve que chaque formule consistante (ou programme logique) admet au moins une extension et que, pour chaque modèle stable d’un programme logique, il existe une extension de son codage logique qui l’implique. Certaines extensions (extra-extensions) ne correspondent pas à des modèles stables du programme logique, mais sont intéressantes car elles représentent ici, une extension pour la sémantique des modèles stables. Nous donnons une condition discriminante simple qui permet de reconnaître les extensions « normales » et les distinguer des extra-extensions. Basé sur cette sémantique, nous proposons une nouvelle méthode de recherche de modèles stables pour les programmes logiques. Elle a l'avantage d'utiliser un ensemble de clauses de Horn et travaille à espace constant. Elle évite ainsi, la lourdeur induite par la gestion des boucles, dont souffrent la plupart des solveurs ASP utilisant la complétion de Clark et qui ont des complexités spatiales exponentielles dans le pire des cas. De plus, l'énumération est effectuée sur un ensemble restreint de variables du programme logique. Ce qui réduit en général, la complexité temporelle de l'algorithme. En plus de la recherche de modèles stables, cette méthode pourrait générer une sorte d'extra-modèles stables exprimant ainsi l'extension portée à la sémantique des modèles stables.

    11h20 -> 11h35 Coffee break

    11h35 -> 12h20 — Raskin Jean-Francois, ULB

    Titre : Assume Admissible Synthesis.

    Abstract :

    In this talk, I will show how the notion of admissibility can be used to provide an elegant solution to the synthesis problem for reactive system where the environment is not completely adversarial or when the system is composed of several components. In particular, I will introduce a novel rule for synthesis of reactive systems, applicable to systems made of n components which have each their own objectives. Contrary to previous proposals in the literature, the rule « assume admissible » defines sets of solutions which are rectangular. This property leads to solutions which are robust and resilient, and allows one to synthesize strategies separately for each component.

    End: 12h30


    Conference : Big Data à la Russe


    07/03/2019 à 00h00

    Dear all, Dyni / PSD / LIS invite you to the 4th Russo-French Big Data Congress at Toulon, 7th & 8th of march 2019 : https://tinyurl.com/y64jjzkb Free entrance, welcome ! Easy access from TGV station Sincerely, Adeline Paiement & Hervé Glotin

    Seminaire : CaNa : Nicolas Behr : An introduction to rule algebras and stochastic mechanics for theories of rewriting


    19/02/2019 à 14h00

    Reference: https://arxiv.org/abs/1807.00785 Abstract: In this talk, without assuming any particular familiarity of the audience with the relevant theory of (M-) adhesive categories, I will provide an introduction to the so-called Double-Pushout (DPO) rewriting framework. Particular emphasis will be given to a novel series of results that concerns a certain form of associativity of the notion of sequential compositions of rewriting rules. In fact, it is this associativity that (via the mathematical framework of rule algebras) permits to make contact between classical notions of manipulations of graphs in combinatorics and statistical physics on the one hand, and the category-theoretical formulation of rewriting theories on the other hand. Some explicit application examples in the field of continuous-time Markov chains based on stochastic DPO-rewriting systems will be presented, including models of dynamical random graph ensembles (such as e.g. a birth-death process on edges of finite graphs).

    Soutenance d'HDR : BAC Alexandra : Analyse et reconstruction de modèles 3D : approches géométriques et topologiques


    07/02/2019 à 14h00

    Mme BAC Alexandra soutiendra son HDR sur le thème : Analyse et reconstruction de modèles 3D : approches géométriques et topologiques, dans l'Amphi A du bâtiment Polytech sur le campus de Luminy.

    Seminaire : MOVE : Bruno Guillon (CRIStAL, Université de Lille)


    07/02/2019 à 10h30

    Titre : Finding paths in large graphs Lieu : Salle de réunion du bâtiment modulaire BP5 (en bas de la BU), Luminy Résumé : When dealing with large graphs, classical algorithms for finding paths such as Dijkstra's Algorithm are unsuitable, because they require to perform too many disk accesses. To avoid this cost, while keeping a data structure of size quasi-linear in the size of the graph, we propose to guide the path search with a distance oracle, obtained from a topological embedding of the graph. I will present fresh experimental research on this topic, in which we obtain graph embeddings using learning algorithms from natural language processing. On some graphs, such as the graph of publications of DBLP, our topologically-guided path search allows us to visit a small portion of the graph only, in average. This is joint work with Charles Paperman.

    Seminaire : CaNa : 22 janvier 2019 à 14h : Sur les délais de communication entre systèmes numériques (microcontrôleurs), BERENGER Cédric


    22/01/2019 à 14h00

    Résumé : Lors de mon stage de recherche, j’avais développé un algorithme de synchronisation pour de grands réseaux sur la base d’un modèle probabiliste de délais de transmission d’un noeud à l'autre. Lors d’essais avec des systèmes réels, nous sommes tombés sur des observations inattendues qui nous obligent de repenser les modèles, mais qui ouvrent aussi des perspectives d'applications très surprenantes en transformant un défaut en un atout. Salle de réunion du bâtiment modulaire, Luminy

    Seminaire : CaNa : SAT est NP-complet, la preuve !


    20/12/2018 à 14h00

    Résumé : Ne croyez pas ce que l'on vous a dit, le théorème de Cook-Levin n'est pas si difficile que cela à démontrer... J'ai longtemps admis cette preuve, et après l'avoir lue dans le livre de Sylvain Perifel, j'ai envie de la partager ! Venez ajouter LA brique de base à vos connaissances en complexité, ou simplement réviser :-) Salle du réunion du bâtiment modulaire, Luminy

    Seminaire : DALGO: Thomas Nowak (LRI), vendredi 14 à 10h30


    14/12/2018 à 10h30

    Title: Approximate Agreement in Dynamic Networks Abstract: Agreeing on a common value in a distributed system is a problem that lies at the heart of many distributed computing problems and occurs in several flavors. Unfortunately, even modest network dynamics already prohibit solvability of exact consensus, where agents have to decide on a single output value that is within the range of the agents' initial values. For many problems (distributed control, clock synchronization, load balancing, ...) it is however sufficient to asymptotically converge to the same value, or decide on values not too far from each other. We study solvability of these consensus variants in highly dynamic networks, provide time complexity results, and present fast algorithms. We then show how the results on dynamic networks are relevant for classical fault-models, such as asynchronous message passing with crashes. The talk is based on joint work with Bernadette Charron-Bost, Matthias Függer, and Manfred Schwarz. Nouvelle salle du conseil, RDC de l'ancienne BU (en entrant à gauche)

    Seminaire : 5ème demi-journée Pole Calcul


    29/11/2018 à 09h30

    Dans le cadre du cycle des demi-journées du Pole Calcul du LIS et exceptionnellement aussi du mois de l’IA*, la prochaine et dernière matinée sera autour du thème “Intelligence artificiel et calcul". Les trois intervenants confirmés sont , Gilles Audemard (CRIL) et Cyril Terrioux (LIS) e Leila Amgoud (IRIT).

    Seminaire : CaNa : Adiabatic methods in quantum control, CHITTARO Francesca


    15/11/2018 à 10h00

    Résumé : Quantum control is the branch of control theory concerned with quantum systems, that is, dynamical systems at atomic scales, that evolve according to the laws of quantum mechanics.

    One fundamental issue in quantum control theory is the controllability of quantum systems, that is, whether is it possible to drive a quantum system to a desired state, by means of suitably designed control fields. To cover most theoretical and practical situations, several notion of controllability have been proposed, as, for instance, controllability in the evolution operator, pure state controllability, controllability in population and eigenstate controllability. After a brief introduction on the topic, I will expose some results on the approximate spread controllability of (closed) quantum systems, obtained by means of adiabatic techniques, and taking advantage of the presence of conical intersections between the energy eigenstates. These results have been published in [1],[2].

    Adiabatic techniques can be successfully used also to study the dynamics of open quantum systems. In particular, in [3] they have been applied to find an effective description of the evolution of open, weakly coupled quantum systems, where the sub-system of interest dissipate with much slower time scales than the rest of the system.

    [1] U. Boscain, F. C. Chittaro, P. Mason, M. Sigalotti Quantum Control via Adiabatic Theory and intersection of eigenvalues IEEE-TAC, (2012) 57, No. 8, 1970--1983
    [2] F. C. Chittaro, P. Mason Approximate controllability via adiabatic techniques for the three-inputs controlled Schrödinger equation, SIAM J. Control Optim., (2017), 55(6), 4202–4226.

    Salle du réunion du bâtiment modulaire, Luminy

    Seminaire : CaNa : Exploring attractor invariance in elementary cellular automata : complexité algorithmique, Stéphanie MacLean


    13/11/2018 à 14h00

    We are interested in the study of the set of attractors of all 256 Elementary Cellular Automata (ECA) , i.e., one-dimensional, binary 3-neighbourhood cellular automata, dened on an n-cell lattice (n is the length of the automaton).

    Recent works have studied the invariance of their attractors against dierent update schemes, and how these aect their dynamics. Specically, in [1] was introduced the notion of k-invariance: an ECA rule r is k-invariant if its set of attractors, denoted by Fr(s), remains invariant for all update schemes s having blocks of length at most k (notice that k=1 stands for sequential update schemes, while k = n is the parallel, or synchronous one). In this context, the 1-invariance was studied in [2], where 104 ECA rules showed to have this kind of invariance. In [1] and [3] the authors studied the k-invariance, for 2 < k ≤ n, for all 104 ECA rules above mentioned.

    In this work, we explore another notion of attractor invariance "in between ECA rules", we say that two ECA rules u and v are attractor equivalent over a set of update schemes S, if given any s in S, Fu(s) = Fv(s). We begin our study with the 1-invariant rules, searching for equivalences between their sets of attractors, for all 4 ≤ n ≤ 14, so as to have a set of rules that are "candidates" to be attractor equivalent, since we know that if u and v are both 1-invariant ECA rules, then their sets of attractors remain invariant, but not necessarily the same, for all sequential update schemes s. Attractor equivalence gives us new insights of the dynamical behaviour of a rule (and its equivalent rules) under dierent update schemes.

    Salle de réunion du bâtiment modulaire, Luminy

    Seminaire : Séminaire d'Analyse et Contrôle des Systèmes


    00/00/0000 à 00h00

    Gabriel Abba 23 Mai 2019