Bandeau du Laboratoire d'Informatique & Systèmes (LIS)

Agenda depuis 2024

Consulter les archives

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