Agenda depuis 2024
Seminaire : Séminaire équipe DALGO : Arnaud Labourel (LIS)
01/10/2024 à 10h30
Place : salle REU 04.05 (LIS Luminy)Title : Graph Exploration: The Impact of a Distance Constraint
Abstract :
In this presentation, we’ll consider a mobile agent moving inside a graph that has to explore all of its nodes and edges using the minimum number of edge traversals. The agent has no a priori knowledge of the graph, but it will gain information by exploring it using a deterministic algorithm. During its exploration, the agent must always respect the constraint of knowing a path of length at most D to go back to its starting node s. The upper bound D is fixed as being equal to (1+α)r, where r is the eccentricity of node s (i.e., the maximum distance from s to any other node) and α is any positive real constant. We consider the penalty of an exploration algorithm that is the number of edge traversals made by the agent in excess of the number of edges of the graph. In 1999, Panaite and Pelc gave an algorithm for solving exploration without any constraint with a penalty linear in the number of nodes of the graph. Hence, a natural question is whether one could obtain a distance-constrained exploration algorithm with the same guarantee as well. In this presentation, we will provide a negative answer to this question.
Joint work with Yoann Dieudonné (MIS Lab., Université de Picardie Jules Verne) and Stéphane Devismes (MIS Lab., Université de Picardie Jules Verne)
Seminaire : Séminaire CANA : Rocco Ascone (Università degli Studi di Trieste)
16/07/2024 à 16h00
Lieu : online et TPR2 04.05Titre : 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 COALATitre : 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.05Titre: 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 ComponentsLieu : 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 ImagingLieu : 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.05Titre : 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 MicroscopyLieu : 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ôtSeminaire : 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 comportementsLieu : 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-endoscopiquesLieu : 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, LuminyTitre : 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 profondeLieu : 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, LuminyTitre : 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, LuminyTitre : 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, LuminyTitre : 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, LuminyTitre : 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, LuminyTitre : 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ésLieu : 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, LuminyTitre : 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, LuminyTitre : 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/seminarsSeminaire : 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, LuminyTitre : 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, LuminyTitre : 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, LuminyTitre : 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, LuminyTitre : 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, LuminyTitre : (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.