Agenda depuis 2024

Seminaire : Séminaire CANA : Nicolas Schabanel

21/01/2025 à 14h00

Title : How do we make DNA origami and what are the challenges we tackle Nicolas Schabanel
Joint work with: Nicolas Levy (LIP), Julie Finkel (CBS), Allan Mills (CBS), Pierre Marcus (LIP), Octave Hazard (LIP), Daria Pchelina (LIP), Joris Picot (LIP) and Gaëtan Bellot (CBS)

Salle : 04.05 TPR2

Abstract :

Curved shapes are ubiquitous in both natural and engineered structures contributing to their intricate functionalities and mechanical resilience. Replicating these shapes at the nanoscale using DNA nanotechnology poses significant challenges due to the inherent constraints of DNA geometry. Here, we introduce a geometric model for curved DNA helices and an algorithm for automatic routing of DNA helices along non-planar trajectories to fold predefined 3D DNA origami nanostructures. We provide an automated design process that enables the self-assembly of curved DNA helix bundles, hollow shapes, nested spheres, and biomimetic structures such as vault-like cages, using a novel spiral-based paradigm. This process, integrated in ENSnano software, revisites DNA origami principles to go beyond current structural confinements and opens opportunities for creating general 3D spatial configurations with advanced programmability for enhanced functional integration. L’exposé sera spécialement conçu pour des personnes qui ne connaissent rien du tout à l’ADN ni au origami ADN.

Seminaire : Séminaire CANA : Antoine Soulas

07/01/2025 à 14h00

Title : Quantifying quantum coherence and the deviation from the total probability formula

Salle : 04.05 TPR2

Abstract :

Quantum coherence is the main resource exploited by quantum computers. Unsurprisingly, over the past few years, there has been a strong interest in the task of finding appropriate measures of coherence. In this talk, we propose a novel approach to quantify quantum coherence which, contrary to the previous ones, does not rely on resource theory but rather on ontological considerations. In this framework, coherence is understood as the ability for a quantum system's statistics to deviate from the total probability formula (TPF). After a recap on the basics of quantum theory, we motivate the importance of the TPF in quantum foundations. We then propose a new set of axioms that a measure of coherence should satisfy, and show that it defines a class of measures different from the main previous proposal. Finally, we prove a general result about the dependence of the l2-coherence norm on the basis of interest, namely that it is well approximated by the square root of the purity in most bases. Such a behaviour is actually expected for any measure of coherence, because of the mathematical phenomenon known as « concentration of measure ».

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

02/12/2024 à 10h00

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

Seminaire : Séminaire CANA : Alexandre Clément

26/11/2024 à 14h00

Lieu : TPR2 04.05

Titre : Complete Equational Theories for Quantum circuits

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

Seminaire : Séminaire CANA : Victor Lutfalla

12/11/2024 à 14h00

Title : Ants on the highway

Salle : 04.05 TPR2

Abstract :

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

Seminaire : Séminaire CANA : Shuwen Kan

05/11/2024 à 15h00

Lieu : online and TPR2 04.05

Titre : A Scalable Quantum Circuit Cutting in a Distributed System

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

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

04/11/2024 à 14h00

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

Seminaire : Analyse de documents juridiques

09/10/2024 à 14h30

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

Seminaire : Séminaire CANA - Tomáš Gonda

08/10/2024 à 14h00

Lieu : TPR2 04.05

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

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

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

01/10/2024 à 14h30

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

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

30/09/2024 à 10h00

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

Seminaire : Séminaire CANA : Pacôme Perrotin

24/09/2024 à 14h00

Lieu : TPR2 04.05

Titre : Recent advancements in consensus problems over automata networks

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

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

16/09/2024 à 10h00

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

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

16/07/2024 à 16h00

Lieu : online et TPR2 04.05

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

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

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

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

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

Rencontre : Journées stagiaires équipe DALGO

02/07/2024 à 09h30

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

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

Conference : Multimodal Information Processing: Some recent NLP applications

24/06/2024 à 10h00

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

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

19/06/2024 à 15h00

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

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

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

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

18/06/2024 à 14h00

Lieu : TPR2 04.05

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

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

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

17/06/2024 à 14h00

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

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

17/06/2024 à 09h00

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

Objectif :

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

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

Equipe organisatrice :

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

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

11/06/2024 à 14h00

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

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

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

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

11/06/2024 à 10h00

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

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

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

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

04/06/2024 à 14h00

Lieu : TPR2 04.05

Titre : Nonclassicality in correlations without causal order

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

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

02/06/2024 à 14h00

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

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

02/06/2024 à 14h00

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

Seminaire : Séminaire I&M - Adrien JULIA

31/05/2024 à 14h00

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

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

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

29/05/2024 à 14h00

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

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

29/05/2024 à 14h00

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

Seminaire : Soutenance de thèse Alexandre Marin GMOD

21/05/2024 à 10h30

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

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

17/05/2024 à 14h00

Titre :Apports d’un système de vision plénoptique pour l’analyse des comportements​
Lieu : Luminy, TPR2 salle de réunion 04.03.
Résumé :

CONTEXTE
Depuis plusieurs décennies, la reconnaissance des expressions faciales est reconnue comme une méthode essentielle pour l'analyse approfondie des émotions humaines, constituant un pilier de l'analyse comportementale moderne. Aujourd'hui, notre compréhension de ce domaine est renforcée par l'intégration de la recherche académique avec des technologies avancées. Le Centre d’Étude et de Recherche en Gestion d’Aix Marseille (CERGAM), en collaboration avec le Laboratoire d’Informatique et Systèmes (LIS) et l’Institut de Mathématiques de Marseille (I2M), explore des applications de ces méthodes au marketing. Grâce aux caméras plénoptiques, qui capturent l'intensité et la direction des rayons lumineux, nous obtenons des images multiperspectives en une seule prise [1, 2]. Ces images, en facilitant la création de cartes de profondeur détaillées, améliorent notre capacité à analyser les nuances des expressions faciales, enrichissant ainsi notre compréhension des réactions émotionnelles des consommateurs.

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

[1] T. -W. Shen et al., "Facial expression recognition using depth map estimation of Light Field Camera," 2016 IEEE International Conference on Signal Processing, Communications and Computing(ICSPCC), 2016, pp.1-4, doi: 10.1109/ICSPCC.2016.7753695.
[2] A. Sepas-Moghaddam, A. Etemad, F. Pereira and P. L. Correia, "Facial Emotion Recognition Using Light Field Images with Deep Attention-Based Bidirectional LSTM," ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2020, pp. 3367-3371, doi: 10.1109/ICASSP40776.2020.9053919.

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

06/05/2024 à 10h00

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

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

29/04/2024 à 10h00

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

Seminaire : Séminaire I&M - Mira Razafindrambao

26/04/2024 à 14h00

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

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

15/04/2024 à 14h30

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

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

08/04/2024 à 10h00

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

Seminaire : Séminaire CANA : Pedro Balbi

02/04/2024 à 14h00

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

Titre : Solving the parity problem in automata networks

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

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

29/03/2024 à 14h00

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

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

28/03/2024 à 09h30

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

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

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

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

25/03/2024 à 10h00

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

Seminaire : Séminaire CANA : Bert Lindenhovius

19/03/2024 à 14h00

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

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

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

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

19/03/2024 à 10h00

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

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

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

Seminaire : Séminaire GMOD : Quentin Wendling

15/03/2024 à 10h00

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

Seminaire : Séminaire CANA : Aidan Chatwin-Davies

12/03/2024 à 14h00

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

Titre : Quantum Information Processing with Gravitating Systems and More

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

Seminaire : Séminaire CANA : Djamel Eddine Amir

28/02/2024 à 14h00

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

Titre : Computable Aspects of Topological Spaces

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

Seminaire : Séminaire CANA : Niall Murphy

27/02/2024 à 14h00

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

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

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

Seminaire : Séminaire I&M - Jules collenne

23/02/2024 à 14h00

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

Seminaire : Séminaire CANA : Léo Gayral

20/02/2024 à 14h00

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

Titre : Uniformly Chaotic Finite-Range Lattice Models

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

Seminaire : Séminaire GMOD : Guillaume Coiffier

16/02/2024 à 10h00

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

Conference : Exploiting Knowledge Graphs in LLM-based Applications

13/02/2024 à 10h00

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

Seminaire : Séminaire GMOD : Nicolas Lutz

09/02/2024 à 10h00

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

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

06/02/2024 à 14h00

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

Titre : Density of disc and sphere packings

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

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

05/02/2024 à 10h00

Séminaire ACRO : Oscar Defrain (05 février, 10h) Titre : Énumération Algorithmique IV. Supergraph method. Résumé : Cet exposé est le quatrième d’une série d’exposés sur le thème de l’énumération algorithmique où sont présentés différentes techniques, résultats et problèmes ouverts dans ce domaine relativement récent. Dans cet épisode, on s’intéressera à une technique d’énumération généralement appelée « supergraph method » qui repose sur le parcours d’un graphe des solutions bien choisi. On s’intéressera en particulier à l’énumération des sous-graphes vérifiant une propriété héréditaire, des arbres couvrant d’un graphe, ou encore à l’énumération des bases d’un matroid. https://acro.lis-lab.fr/seminars

Seminaire : Séminaire GMOD : Sylvain Gerbaud

02/02/2024 à 10h00

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

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

01/02/2024 à 09h30

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

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

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

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

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

30/01/2024 à 14h00

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

Titre : All You Need to Know about the Quantum Switch

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

Conference : Sémnaire MoVe anvec Chana Weil-Kennedy

26/01/2024 à 10h30

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

Seminaire : Séminaire CANA : Martin Plávala

23/01/2024 à 14h00

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

Titre : Optimization in quantum information: from foundations to applications

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

Seminaire : Séminaire ACRO : Yann Strozecki

22/01/2024 à 13h00

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

Seminaire : Séminaire CANA : Victor Lutfalla

16/01/2024 à 14h00

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

Titre : Bootstrap percolation on Penrose tilings

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

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

16/01/2024 à 10h30

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

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

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

Seminaire : Séminaire CANA : Simon Milz

09/01/2024 à 14h00

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

Titre : (Some) consequences of invasiveness in quantum mechanics

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

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

08/01/2024 à 10h00

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