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

Agenda depuis 2024

Consulter les archives

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