Agenda depuis 2023
Seminaire : Séminaire CANA : Julian Wechs
10/10/2023 à 14h00
Titre: Subsystem decompositions of quantum circuits and processes with indefinite causal orderRésumé : One can theoretically conceive of situations in which the causal order between quantum operations is no longer well-defined. Such causally indefinite processes are of interest from a foundational perspective, but could also open up new possibilities in quantum information, as they go beyond the conventional paradigm of quantum circuits. A central question is which of these processes have an operational interpretation or physical realisation, and, more particularly, whether indefinite causal order could be realised within standard physics. It has been shown that certain causally indefinite processes can take place as part of standard quantum mechanical evolutions, described by acyclic quantum circuits, if the latter are represented with respect to an alternative choice of quantum subsystems that can be delocalised in time. In this seminar, I will present a general framework to describe such transformations between different subsystem decompositions of quantum circuits. This puts the notion that indefinite causal order is realisable in standard quantum theory on a rigorous footing. Based on Nat. Commun. 14, 1471 and work in preparation.
Rencontre : Le LIS à la Nuit Européenne des Chercheurs 2023
29/09/2023 à 18h00
Nous vous donnons rendez-vous ce vendredi 29 septembre de 18h à 23h30 aux Docks des Suds à Marseille pour la Nuit Européenne des Chercheurs, soirée festive et riche de culture scientifique grand public. Au sein du "Bureau de Désinformation", Valentin Emiya (LIS) et Anne Mathieu (INS) se risqueront à aborder la question "Les jeux vidéos peuvent-ils rendre intelligents?". Plus d'informations: http://url.univ-amu.fr/nuit-chercheurs-2023 .Seminaire : Séminaire ACRO : Guyslain Naves
25/09/2023 à 10h00
Titre : Plongement dans L1 de métriques planaires préservant les distances entre sommets d'une même face. Résumé : Le théorème d'Okamura-Seymour affirme que les métriques induites par un graphe planaire sur les sommets de sa face extérieure sont plongeables dans L1. Une conjecture fameuse est que toute métrique induite par un graphe planaire est plongeable dans L1 avec une distortion constante. Je présenterai un article récent de Nikhil Kumar (FOCS 2022) qui étend le théorème d'Okamura-Seymour et constitue une avancée vers cette conjecture : tout graphe planaire G est plongeable dans L1, de sorte que pour toute face F, la métrique induite sur cette face subit une distortion constante.Seminaire : Séminaire ACRO : Victor Chepoi
11/09/2023 à 10h00
Titre : Separation axioms S3 and S4 in convexity spaces and graphs. Résumé court : In the talk, we will present old and new results about the separation by halfspaces of pairs of disjoint convex sets (S4) and of points and convex sets (S3).WorkShop : Workshop on Management of Data under Uncertainty (MoDU 2023) @ADBIS 2023
04/09/2023 à 09h00
1st Workshop on Management of Data under Uncertainty (MoDU 2023) @ ADBIS 2023 Barcelona, Spain Website: https://modu2023.lis-lab.fr/ The aim of the workshop is to allow academics and industrial from various areas to share their experiences on management of uncertain data (Uncertainty in data collection and querying, Uncertainty in ML and Deep learning models, Uncertainty in data analytics). ** WORKSHOP ORGANIZERS ** • Richard Chbeir, University Pau & Pays Adour, Anglet, France • Allel Hadjali, Engineer School ENSMA, Poitiers, France • Sana Sellami, Aix Marseille University, Marseille, FranceSeminaire : Séminaire CANA : Kévin Perrot
11/07/2023 à 11h00
Titre : Une preuve du premier théorème d’incomplétude de Gödel avec la complexité de Kolmogorov Lieu : TPR2/04.05 (Luminy) Résumé : Je propose de tenter cette preuve, due à Chaitin. Elle repose sur une formalisation du paradoxe de Berry : soit l’expression « le plus petit entier positif qui n’est pas définissable en moins de seize mots ». Cette expression définit cet entier en moins de seize mots, ce qui est paradoxal. Pour celles et ceux qui ne connaissent rien aux théorèmes d’incomplétude de Gödel et/ou à la calculabilité, je recommande de visionner les deux vidéos suivantes pour vous échauffer (10 minutes chacune) : https://www.arte.tv/fr/videos/097454-007-A/voyages-au-pays-des-maths et https://www.arte.tv/fr/videos/097454-005-A/voyages-au-pays-des-maths/. Ce séminaire n’attend aucun pré-requis de son auditoire, on pourra discuter de tout (en particulier de ce que disent les énoncés des théorèmes d’incomplétude de Gödel) et j’espère bien que vous aurez des questions pour m’aider à savoir quoi vous raconter (sinon, pour la preuve en elle-même, en 5 minutes c’est plié…).Conference : Séminaire ACRO : Feodor Dragan (26 juin, 10h)
26/06/2023 à 10h00
Titre : α_i-Metric Graphs: Radius, Diameter and all Eccentricities Résumé : We extend known results on chordal graphs and distance-hereditary graphs to much larger graph classes by using only a common metric property of these graphs. Specifically, a graph is called α_i-metric (i∈\mathcal{N}) if it satisfies the following α_i-metric property for every vertices u,w,v and x: if a shortest path between u and w and a shortest path between x and v share a terminal edge vw, then d(u,x) ≥ d(u,v) + d(v,x) - i. Roughly, gluing together any two shortest paths along a common terminal edge may not necessarily result in a shortest path but yields a ``near-shortest'' path with defect at most i. It is known that α_0-metric graphs are exactly ptolemaic graphs, and that chordal graphs and distance-hereditary graphs are α_i-metric for i=1 and i=2, respectively. We show that an additive O(i)-approximation of the radius, of the diameter, and in fact of all vertex eccentricities of an α_i-metric graph can be computed in total linear time. Our strongest results are obtained for α_1-metric graphs, for which we prove that a central vertex can be computed in subquadratic time, and even better in linear time for so-called (α_1,Δ)-metric graphs (a superclass of chordal graphs and of plane triangulations with inner vertices of degree at least 7). The latter answers a question raised in (Dragan, IPL, 2020). Our algorithms follow from new results on centers and metric intervals of α_i-metric graphs. In particular, we prove that the diameter of the center is at most 3i+2 (at most 3, if i=1). The latter partly answers a question raised in (Yushmanov & Chepoi, Mathematical Problems in Cybernetics, 1991). This is a joint work with Guillaume Ducoffe.Seminaire : Séminaire/cours CANA : Enrico Formenti
20/06/2023 à 14h00
Orateur : Enrico Formenti (I3S)Lieu : TPR2/04.05 (Luminy)
Titre : Introduction aux séries formelles
Résumé : Les séries formelles (SFs) sont un outil fondamental dans l’analyse combinatoire mais aussi dans l’analyse complexe. Dans ce cours/séminaire nous chercherons à donner un petit aperçu du rôle joué par les SFs dans des contextes assez différents. Le cours est donc structuré en plusieurs parties. Dans cette première partie nous parlerons de récurrences (linéaires et non) et montrerons comment les SFs puissent (dans certains cas) aider à trouver les termes généraux de ces récurrences. Nous montrerons aussi à l’occasion des liens avec les systèmes dynamiques discrets.
Seminaire : Séminaire ACRO : Alixel Bagnis (19 juin, 10h)
19/06/2023 à 10h00
Titre : Énumération des signatures d'une CNF. Résumé : Si Φ = C1 ∧ C2 ∧ … ∧ Cm est une CNF et 𝓪 est un assignement, alors la signature de 𝓪 sur Φ est le mot binaire s où le i-ème bit est à 1 si et seulement si 𝓪 évalue Ci à 1. On appelle un mot binaire de taille m une signature de Φ s’il existe un assignement dont il est la signature sur Φ. La signature vient traduire le fait qu’il existe un assignement qui satisfait telles et telles clauses et ne satisfait pas telles ou telles clauses. En particulier Φ est satisfiable ssi 111…1 est une signature. De ce fait, décider si s est la signature d'une 3-CNF est NP-complet. Malgré tout et de façon assez étonnante, Berczi et al. montrent que l'énumération de toutes les signatures d'une CNF quelconque reste possible en temps incrémental polynomial. L'objet de cet exposé est de présenter le problème, l'algorithme de Berczi et al., et de distinguer quelques questions ouvertes qui ont été l'objet de ce stage.Seminaire : Demi Journées du Pôle Calcul
15/06/2023 à 09h30
Speaker : Liva Ralaivola (Criteo AI Lab)Title : Differentially-Private Sliced Wasserstein Distance
Absrtract : Developing machine learning methods that are privacy preserving is today a central topic of research, with huge practical impacts. Among the numerous ways to address privacy-preserving learning, we here take the perspective of computing the divergences between distributions under the Differential Privacy (DP) framework --- being able to compute divergences between distributions is pivotal for many machine learning problems, such as learning generative models or domain adaptation problems. Instead of resorting to the popular gradient-based sanitiziation method for DP, we tackle the problem at its roots by focusing on the Sliced Wasserstein Distance and seamlessly making it differentially private. Our main contribution is as follows: we analyze the property of adding a Gaussian perturbation to the intrinsic randomized mechanism of the Sliced Wasserstein Distance, and we establish the sensitivity of the resulting differentially private mechanism. One of our important finding is that this DP mechanism transforms the Sliced Wasserstein distance into another distance, that we call the Smoothed Sliced Wasserstein Distance. This new differentially-private distribution distance can be plugged into generative models and domain adaptation algorithms in a tranparent way, and we empirically show that it yields highly competitive performance compared with gradient-based DP approaches from the literature, with almost no loss in accuracy for the domain adaptation problems that we consider. (Joint work with A. Rakotomamonjy (Criteo AI Lab))
11:00 - 11:30
Speaker : Van-Giang Trinh (LIRICA, LIS)
Title: Efficient enumeration of fixed points in complex Boolean networks using answer set programming
Abstract: Boolean Networks (BNs) are an efficient modeling formalism with applications in various research fields such as mathematics, computer science, and more recently systems biology. One crucial problem in the BN research is to enumerate all fixed points, which has been proven crucial in the analysis and control of biological systems. Indeed, in that field, BNs originated from the pioneering work of R. Thomas on gene regulation and from the start were characterized by their asymptotic behavior: complex attractors and fixed points. The former being notably more difficult to compute exactly, and specific to certain biological systems, the computation of stable states (fixed points) has been the standard way to analyze those BNs for years. However, with the increase in model size and complexity of Boolean update functions, the existing methods for this problem show their limitations. To our knowledge, all the state-of-the-art methods for the fixed point enumeration problem rely on Answer Set Programming (ASP). Motivated by these facts, in this work we propose two new efficient ASP-based methods to solve this problem. We evaluate them on both real-world and pseudo-random models, showing that they vastly outperform four state-of-the-art methods as well as can handle very large and complex models.
https://demi-journees-pole-calcul.lis-lab.fr/
Seminaire : Séminaire ACRO : Oscar Defrain (12 juin, 10h)
12/06/2023 à 10h00
Titre : Minimal dominating sets enumeration with FPT-delay parameterized by the maximum degree Résumé : At STOC 2002, Eiter, Gottlob, and Makino presented a technique called ordered generation that yields an n^{O(d)}-delay algorithm listing all minimal transversals of an n-vertex hypergraph of degeneracy d, for an appropriate definition of degeneracy. Recently at IWOCA 2019, Conte, Kanté, Marino, and Uno asked whether, even for a more restrictive notion of degeneracy, this XP-delay algorithm parameterized by d could be improved to an FPT-delay algorithm parameterized by d and the maximum degree ∆, i.e., an algorithm with delay f(d, ∆) · n^{O(1)} for some computable function f. We answer this question in the affirmative whenever the hypergraph corresponds to the closed neighborhoods of a given graph, i.e., we show that the intimately related problem of enumerating minimal dominating sets in graphs can be solved with FPT-delay parameterized by the degeneracy and the maximum degree https://acro.lis-lab.fr/seminarsSeminaire : Séminaire MoVe avec Elli Anastasiadi
08/06/2023 à 10h30
ui ? Elli Anastasiadi (Uppsala University) Quand ? jeudi 8.6 à 10h30 Où ? 4.05 au TPR2 comme d'habitude, et en ligne sur demande (il faut demander) On pourra aussi suivre ca ensemble dans la salle usuelle 4.05 au TPR2. Quoi ? Verification of weak memory models Mais encore ? Distributed algorithms and architectures are everywhere, and along with them bring faster computation and harder verification. In the heart of the verification effort lies always the the understanding of how exactly a piece of software can execute, and it is exactly there where parallelism and concurrency introduce extra potential execution scenaria and complicate the process. The concept of weak memory approaches this issue from an applied perspective, where the implementation of a system is what defines what potential executions can occur. Unfortunately the outcome is usually that many, additional to the expected ones, program behaviours are present, and thus the program's safety is even more at risk. In this talk we will first look at exactly how weak memory presents itself through different implementations and then discuss some important concepts and problems about the verification of programs in those circumstances.Seminaire : Séminaire CANA : Van-Giang Trinh
30/05/2023 à 14h00
Orateur : Van-Giang Trinh (LIS)Lieu : TPR2/04.05 (Luminy)
Titre : Trap spaces of Boolean networks are conflict-free siphons of their Petri net encoding
Abstract : Boolean network modeling of gene regulation but also of post-transcriptomic systems has proven over the years that it can bring powerful analyses and corresponding insight to the many cases where precise biological data is not sufficiently available to build a detailed quantitative model. Besides simulation, the analysis of such models is mostly based on attractor computation, since those correspond roughly to observable biological phenotypes. The recent use of trap spaces made a real breakthrough in that field allowing to consider medium-sized models that used to be out of reach. However, with the continuing increase in model size and complexity of Boolean update functions, the state-of-the-art computation of minimal trap spaces based on prime-implicants shows its limits due to the difficulty of the prime-implicant computation.
In this article we explore and prove for the first time a connection between trap spaces of a general Boolean network and siphons of its Petri net encoding. Besides important theoretical applications in studying properties of trap spaces, the connection enables us to propose an alternative approach to compute minimal trap spaces, and hence complex attractors, of a general Boolean network. It replaces the need for prime-implicants by a completely different technique, namely the enumeration of maximal siphons in the Petri net encoding of the original model. We then demonstrate its efficiency and compare it to the state-of-the-art methods on a large collection of real-world and randomly generated models.
Conference : ORASIS 2023
22/05/2023 à 00h00
La 19ième édition du colloque d’ORASIS, journées francophones des jeunes chercheurs en vision par ordinateur, se déroulera du 22 au 26 mai 2023 à Carqueiranne (Var, PACA). Elle sera organisée par l'équipe Signal et Image du Laboratoire d'Informatique et Systèmes UMR7020, au centre vacanciel Miléade à Carqueiranne. Ce colloque vise à réunir de jeunes chercheurs francophones (doctorants et jeunes docteurs) issus de la communauté de la vision par ordinateur ou de domaines connexes, avec l'ambition de favoriser, dans une ambiance conviviale, les échanges entre les participants, notamment entre les jeunes chercheurs et chercheurs expérimentés dans le domaine. Les journées seront rythmées par des sessions plénières ainsi que des sessions posters. Plusieurs sessions (7) de conférenciers invités complètent le déroulement de ces journées. Plus d'informations et soumissions: https://orasis2023.sciencesconf.org/Seminaire : Séminaire ACRO : Guyslain Naves (15 mai, 4.05 10h)
15/05/2023 à 10h00
Titre : Répartiteur dans les réseaux de convoyeurs Résumé : Lors d'un précédent exposé, j'avais introduit les réseaux de convoyeurs, modélisant le transport de matériaux sur des tapis roulants et utilisant des appareils nommés splitters et permettant d'uniformiser les charges entre deux tapis. Dans cet exposé, après un rappel des notions, je montrerais comment construire des réseaux permettant d'uniformiser les charges d'un nombre arbitraire de tapis avec aussi peu de splitters que possible. Je prouverai des bornes inférieures sur le nombre de splitters nécessaires, et selon le temps aborderai quelques résultats supplémentaires de complexité. Il n'est pas nécessaire d'avoir vu l'exposé précédent pour suivre celui-ci.Seminaire : Séminaire I&M - Adrien JULIA
12/05/2023 à 14h00
Titre :Post-processings of Light Sheet Fluorescence Microscope Images using autoencoders and Richardson-Lucy deconvolutionLieu : Luminy, TPR2 salle de réunion 04.03.
Résumé :
Light Sheet Fluorescence Microscopy is useful for neurobiologists but may induce artifacts on reconstructed 3D volumes. A three-step pipeline is proposed to improve the quality of slice-by-slice images. It includes a 2D deconvolution algorithm, automatic contrast enhancement, and a convolutional denoising autoencoder to remove noise. Additionally, a new approach is proposed to solve the axial distortion problem using an autoencoder trained on calibration bead images. This pipeline enhances the understanding of biological images by surpassing existing methods.
Seminaire : Séminaire CANA : Eurico Ruivo
02/05/2023 à 14h00
Orateur : Eurico Ruivo (Universidade Presbiteriana Mackenzie, Brazil) Lieu : TPR2/04.05 (Luminy)Titre : An asynchronous solution to the synchronisation problem for binary one-dimensional cellular automata Abstract: Because cellular automata rely on totally local and synchronous processing at the neighbourhood of each cell, the issue of global synchronisation of the cell states has a long tradition in cellular automata literature. In order to solve the synchronisation problem in periodic boundary condition, a rule needs to be conceived so as to lead any initial configuration to converge to a cyclic regime of period 2 characterised by all cells alternating between fully homogeneous configurations of 0s and 1s. In spite of its simplicity, the problem has been shown not to have a solution by synchronously updating the cell states. In contrast, we provide a solution to the problem, with a 4-neighbour rule, by replacing the synchronous update of the cells of the lattice with a deterministic, block sequential asynchronous update schedule.
Seminaire : Séminaire ACRO : Mathieu Mari (17 avril, REU 04.05, 10h)
17/04/2023 à 10h00
Orateur : Mathieu Mari (MIMUW, Université de Varsovie). Titre : A (2+ɛ)-Approximation Algorithm for Maximum Independent Set of Rectangles. Résumé : We study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overlapping rectangles of maximum cardinality. In a recent breakthrough, Mitchell obtained the first constant-factor approximation algorithm for MISR. His algorithm achieves an approximation ratio of 10 and it is based on a dynamic program that intuitively recursively partitions the input plane into special polygons called corner-clipped rectangles (CCRs), without intersecting certain special horizontal line segments called fences. In this talk, I will present a (2+ɛ)-approximation algorithm for MISR which is also based on a recursive partitioning scheme. First, we use a partition into a class of axis-parallel polygons with constant complexity each that are more general than CCRs. This allows us to provide an arguably simpler analysis and at the same time already improves the approximation ratio to 4. Then, using a more elaborate charging scheme and a recursive partitioning into general axis-parallel polygons with constant complexity, we improve our approximation ratio to 2+ɛ. In particular, we construct a recursive partitioning based on more general fences which can be sequences of up to O(1/ɛ) line segments each. This partitioning routine and our other new ideas may be useful for future work towards a PTAS for MISR. At the end of the talk, I will present a bunch of future research directions related to the problem. This is a joint work with Waldo Gálvez, Arindam Khan, Tobias Mömke, Madhusudhan Reddy and Andreas Wiese.Seminaire : Séminaire ACRO : Colin Geniet
12/04/2023 à 00h00
Titre : Twin-width of groups and bounded degree graphs Résumé : Twin-width is a graph invariant introduced by Bonnet, Kim, Thomassé, and Watrigant, with notable applications in logic, FPT algorithms, and graph coloring. When considering graphs of bounded degree, finiteness of twin-width is stable under quasi-isometries, and thus it defines an invariant of the Cayley graphs of a group. For a group G, having finite twin-width is equivalent to admitting a total order for which the self-action by product avoids some permutations as patterns, which makes twin-width a far reaching generalisation of the notion of orderable groups. Several well-known classes of groups have finite twin-width: abelian groups, solvable groups, groups with polynomial growth, and hyperbolic groups. On the other hand, the class of all cubic graphs is known to have unbounded twin-width by a counting arguments: for any k, there are only n!c^n graphs of twin-width k on vertices {1,...,n} for some constant c (we say that it is a _small_ class of graphs), which is asymptotically less than the number of cubic graphs. Using an embedding theorem of Osajda, we adapt this construction to prove that there are groups with infinite twin-width. The Cayley graphs of such groups induce classes of graphs which are small but have unbounded twin-width, answering a question from previous works. Unfortunately, because these constructions are enumerative and probabilistic, it is essentially impossible to understand the resulting group. Finding an explicit construction for graphs with bounded degree (or groups) and unbounded twin-width remains a major open problem. This is joint work with Édouard Bonnet, Romain Tessera, and Stéphan Thomassé.Seminaire : Séminaire ACRO : Clément Dallard
03/04/2023 à 10h00
Titre : Introduction to tree-independence number Résumé : Tree decompositions are a common and useful data structure for designing dynamic programming algorithms for graph problems. In order to obtain efficient algorithms, one looks for a tree decomposition of the input graph that minimizes some measure on the subgraphs induced by the bags. For instance, when this measure is the number of vertices, we obtain the well-known notion of treewidth. In this talk, the considered measure is the independence number. The independence number of a tree decomposition of a graph G is the smallest integer k such that each bag induces a subgraph with independence number at most k. The tree-independence number of G is defined as the minimum independence number over all tree decompositions of G. Given a tree decomposition with bounded independence number, the Maximum Weight Independent Set and several related NP-hard problems can be solved in polynomial time. We will discuss how to compute tree decompositions with bounded independence number efficiently (when they exist), the algorithmic use of such tree decompositions, and the strong relationship with the notion of (tw,ω)-boundedness.Seminaire : Séminaire I&M - Sabrine djedjiga OUCHERIF
31/03/2023 à 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é :
Durant les quatre dernières décennies, le problème de l’analyse du comportement a été largement étudié dans la communauté scientifique. L’étude de la reconnaissance des expressions faciales représente l’approche la plus abordée qui permet de traiter et d’analyser le comportement humain à travers ses émotions.
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) aspirent à développer les recherches de l’analyse comportementale dans le domaine du marketing en exploitant les performances des caméras plénoptiques[1, 2].Ce système de vision, appelé également photographie en champ lumineux(en anglais: light field (LF)camera), permet d’acquérir des informations sur l’intensité et la direction d’arrivée des rayons lumineux. De ce fait, nous pouvons obtenir des images représentant différents points de vue de la même scène en une seule prise et construire une carte de profondeur.
L’objectif de ce projet est d’étudier et d’analyser le comportement des personnes dans une surface de vente. Pour y parvenir, nous nous intéresserons d’un coté à l’analyse et la reconnaissance des expressions faciales, et de l’autre, à l’estimation de la position du regard à partir des informations renvoyées par les caméras plénoptiques. Concernant le premier point, différentes architectures de réseaux de neurones seront développées afin de traiter les informations renvoyées par les images LF.
[1] T. -W. Shenet 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.
Seminaire : Séminaire pôle ACS - David Hill
30/03/2023 à 14h00
Titre : Reproductibilité et répétabilité des simulations stochastiques Résumé : L'un des critères majeurs de la scientificité d'une étude de recherche est la reproductibilité. Dans cet exposé, nous présenterons les principales définitions autour de la reproductibilité, elles ont évolué récemment à l’ACM en 2020. Nous examinerons dans quelle mesure les travaux d'informatique et de simulation sont concernés. Nous donnerons quelques exemples d'applications incluant des simulations stochastiques parallèles, qui sont trop souvent présentées comme non reproductibles. Toute personne souhaitant produire un travail scientifique en simulation a intérêt à prêter attention à la reproductibilité numérique de ses résultats. Des différences significatives peuvent être observées dans les résultats de simulations parallèles si les meilleures pratiques ne sont pas appliquées. Nous verrons que même dans ce contexte, il est possible de reproduire les mêmes résultats numériques en mettant en œuvre une méthode rigoureuse testée jusqu'à un milliard de threads. Il est ainsi possible de vérifier les résultats parallèles avec leurs contreparties séquentielles et ce avant un passage « à l'échelle », gagnant ainsi en confiance dans les modèles développés. Ce séminaire présentera quelques bonnes pratiques pour des simulations stochastiques parallèles, permettant même de faire face erreurs silencieuses qui impactent les supercalculateurs (dont la machine Exascale présentée l’an passé à Hambourg).Seminaire : Séminaire ACRO : Benjamin Bergougnoux
27/03/2023 à 00h00
Titre : A logic-based algorithmic meta-theorem for mim-width Résumé : We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints (𝖠&𝖢 𝖣𝖭 for short) which extends existential 𝖬𝖲𝖮𝟣 with predicates for querying neighborhoods of vertex sets and for verifying connectivity and acyclicity of vertex sets in various powers of a graph. Building upon [Bergougnoux and Kanté, ESA 2019; SIDMA 2021], we show that the model checking problem for every fixed 𝖠&𝖢 𝖣𝖭 formula is solvable in n^O(w) time when the input graph is given together with a branch decomposition of mim-width w. Nearly all problems that are known to be solvable in polynomial time given a branch decomposition of constant mim-width can be expressed in this framework. We add several natural problems to this list, including problems asking for diverse sets of solutions. Our model checking algorithm is efficient whenever the given branch decomposition of the input graph has small index in terms of the d-neighborhood equivalence [Bui-Xuan, Telle, and Vatshelle, TCS 2013]. We therefore unify and extend known algorithms for tree-width, clique-width and rank-width. Our algorithm has a single-exponential dependence on these three width measures and asymptotically matches run times of the fastest known algorithms for several problems. This results in algorithms with tight run times under the Exponential Time Hypothesis (𝖤𝖳𝖧) for tree-width and clique-width; the above mentioned run time for mim-width is nearly tight under the 𝖤𝖳𝖧 for several problems as well. Our results are also tight in terms of the expressive power of the logic: we show that already slight extensions of our logic make the model checking problem para-𝖭𝖯-hard when parameterized by mim-width plus formula length.Rencontre : PhDays'2023 du LIS
22/03/2023 à 09h00
(English version bellow)La journée des doctorante du LIS aura lieu le mercredi 22 mars 2023 à Luminy, dans amphithéâtre de l'Hexagone (nouvelle BU).
La participation est gratuite, sur inscription. Pour cela vous pouvez remplir le framacalc reçu par courriel, ou bien informer directement par email l'un.e des organisateur.trice. Une courte présentation de votre travail (seul ou en groupe) d'environ 10 minutes par personne, serait grandement appréciée !
Le programme (très) provisoire de la journée sera composé le matin de sessions de présentation entrecoupées d'une pause café, le repas de midi est offert aux participants, puis l'après-midi des activités sportives/sociales seront proposées pour profiter du cadre de Luminy !
Si vous avez des propositions ou remarques, n'hésitez pas à nous contacter.
Merci d'avance pour vos retours,
Elie Antoine, Alexandre Coppé, Raphael Gass, Emmanuelle Salin, Kévin Perrot
--
The PhD student day of the LIS will take place on Wednesday 22nd March 2023 at Luminy, in the amphitheatre of the Hexagone building (new library).
Paticipation is free, but registration is required. For this you can fill the framacalc received by email, or inform directly by email one of the organizers. A short presentation of your work (alone or by group) of around 10 minutes would be much appreciated!
The (very) provisional program of the day will be composed of scientific sessions in the morning, with coffee break, then a lunch offered to the participants, and during the afternoon some social/sport activities to enjoy the Luminy campus!
If you have any question or remark, feel free to contact us.
Thanks in advance for your participation,
Elie Antoine, Alexandre Coppé, Raphael Gass, Emmanuelle Salin, Kévin Perrot
Seminaire : Séminaire ACRO : Jean-Florent Raymond (20 mars, 10h)
20/03/2023 à 10h00
Titre : A lower bound for constant-size local certification Résumé : Given a graph property, a local certification is a labeling that allows to locally check that the property is satisfied. The quality of a certification is measured by the size of its labels: the smaller, the better. This can be seen as a measure of the locality of a property (where properties that can be certified with "small" labels are considered more local than the others). An active line of research is to identify the optimal label size for a given graph property. It turns out that properties can be classified into three important regimes: the properties for which the optimal size is polynomial in the number of vertices of the graph, the ones that require only polylogarithmic size, and the ones that can be certified with a constant number of bits. The first two regimes are well studied, with several upper and lower bounds, specific techniques, and active research questions. On the other hand, the constant regime has never been really explored, at least on the lower bound side. In this talk I will present the first non-trivial lower bound for this low regime: k-colorabilty cannot be certified with just one bit.Seminaire : Séminaire MoVe avec K.S. Chana Weil-Kennedy
16/03/2023 à 10h30
Title : Observation Petri Nets Abstract : Petri nets are a classic formal model for concurrent systems, extensively studied and used since the 1970s. They model fundamental features of concurrent systems such as synchronization, process creation, and choice. Many subclasses of Petri nets have been defined by forbidding one or more of these features (e.g. T-systems, free-choice nets, communication-free nets). In our work, we introduce a feature of Petri nets called observation, which is a restricted form of synchronization. We give a syntactic definition of a class of Petri nets in which the only possible form of synchronization is observation. We study the complexity of analysis problems for this class, called observation Petri nets, and in particular we consider verification problems parameterized by the number of tokens (or processes) in the Petri net. The main analysis problems we study are the class of generalized reachability problems. This class extends reachability queries to possibly infinite sets of markings (or configurations). It includes the cube-reachability problem, which given two sets asks if there is a marking in the first set which can reach a marking in the second set. We show that this class of problems can be decided in polynomial space for observation Petri nets. The classic reachability problem asking if a marking can reach another is also in polynomial space for our observation Petri nets (versus non primitive recursive for general Petri nets). So our results show that it is not harder to check reachability between single markings than it is to check reachability between possibly infinite sets of markings. Thus the observation feature captures a non-trivial property of Petri nets that is particularly interesting for parameterized verification.Seminaire : Séminaire ACRO : Laurent Viennot
13/03/2023 à 10h00
Title : Temporalisation of walks/edges in a graph. Abstract : In a temporal graph, each edge appears and can be traversed at specific points in time. In such a graph, temporal reachability of one node from another is naturally captured by the existence of a temporal path where edges appear in chronological order. Inspired by the optimisation of bus/metro/tramway schedules in a public transport network, we consider the problem of turning a collection of walks (called trips) in a directed graph into a temporal graph by assigning a starting time to each trip so as to maximise the reachability among pairs of nodes. Each trip represents the trajectory of a vehicle and its edges must be scheduled one right after another. Setting a starting time to the trip thus forces the appearing time of all its edges. We call such a starting time assignment a trip temporalisation. We obtain several results about the complexity of maximising reachability via trip temporalisation. Among them, we show that maximising reachability via trip temporalisation is hard to approximate within a factor $\sqrt{n}/12$ in an $n$-vertex digraph, even if we assume that for each pair of nodes, there exists a trip temporalisation connecting them. On the positive side, we show that there must exist a trip temporalisation connecting a constant fraction of all pairs if we additionally assume symmetry, that is, when the collection of trips to be scheduled is such that, for each trip, there is a symmetric trip visiting the same nodes in reverse order. We will also discuss the basic problem of assigning times to the edges of a directed graphs so as to maximise temporal reachability.Seminaire : Séminaire ACRO : Valentin Bartier
06/03/2023 à 10h00
Titre : Reconfiguration d’ensembles indépendants dans les graphes peu denses • Résumé : Le problème de reconfiguration d’ensembles indépendants appartient au domaine plus large des problèmes de reconfiguration combinatoire. Il se formule de la manière suivante : étant donné une collection de jetons placés sur les sommets d’un ensemble indépendant d’un graphe, est-il possible de déplacer un à un ces jetons vers un autre ensemble indépendant cible, de telle sorte que deux jetons ne soient jamais voisins tout au long de la transformation ? Après une introduction générale sur la reconfiguration combinatoire et sur le problème de reconfiguration d’ensembles indépendants, nous nous concentrerons sur la variante du « Token Sliding ». Dans cette variante, une étape de la transformation consiste à déplacer un jeton d’un sommet vers un sommet voisin. Nous nous intéresserons plus particulièrement à la complexité paramétrée de ce problème dans des classes de graphes peu denses et aux nouveaux outils que nous avons récemment développé pour l’élaboration d’algorithmes FPT.Seminaire : Développement de systèmes multi-agents et application en environnement
02/03/2023 à 14h00
Le thème est la simulation de dynamiques urbaines (bidonvilles) par SMA (Système Multi-Agents) avec en arrière-plan des questions d’apprentissage supervisé des agents. L’un des enjeux est d’avoir des modèles explicables aux experts et permettant d’intégrer leur connaissance. Ce travail a lieu dans le cadre d’une convention CIFRE avec une entreprise calédonienne et s’inscrit dans le projet ANR SITI porté par F. Flouvat (équipe DANA).Conférencier : Etienne Tack (doctorant 2A, Insight & Univ Nouvelle Calédonie).
Lieu : LIS St Jérôme (Bat. Polytech).
Salle : Salle de Réunion Nord (Salle de réunion au 1er étage nord).
Lien Zoom : https://univ-amu-fr.zoom.us/j/84340041505?pwd=b0tudEpwYVJkSTA5ZHQwS3BJT2czdz09
Seminaire : Séminaire ACRO : Owen Rouillé (INRIA, Paris)
13/02/2023 à 10h00
Le prochain séminaire de l'équipe ACRO sera donné par Owen Rouillé (INRIA, Paris) qui nous parlera de l'utilisation de l'ordinateur pour aider à formuler ou prouver des conjectures mathématiques, notamment en géométrie. Titre : Experimenting in mathematics: examples of data generation and visualisation Résumé : Mathematics include many complex objects which are difficult to understand. In particular, intuition is crucial in teaching and research, allowing to state and prove conjectures. Building this intuition requires looking at and analysing many examples. Computers are very important tools at our disposal: they allow to generate and analyse large quantities of data, and visualise patterns that would be difficult to draw by hand. However, using them is not straightforward, and implementation raises many new questions, among which the encoding and the performances for instances. The talk is dedicated to the use of computers to help with mathematics. First, I will present part of the work I did during my PhD concerning the computation of two topological invariants for 3-manifolds (Turaev--Viro invariants and hyperbolic volume). These projects illustrate the use of computers in mathematics in a domain where the computations can be difficult and the datasets very large. Then, I will present the main project of my postdoc: the computation and the representation of limit sets in S^3, with a focus on triangular groups.WorkShop : Journées Revêtements
13/02/2023 à 00h00
Les premières Journées Marseillaises des Revêtements auront lieu à Marseille les 13 et 14 février 2023. Ce premier événement se concentrera sur l'utilisation des revêtements de graphes et de leurs généralisations pour l'étude des réseaux anonymes.
Objectifs des Journées
Les revêtements de graphes, et leurs généralisations, ont été introduits et utilisés par Angluin en 1980 pour étudier des problèmes de calcul distribué dans les réseaux anonymes. Les travaux des années 90 et du début des années 2000 (Yamashita et Kameda ; Boldi et Vigna ; Métivier et al) ont démontré l'utilité de ces outils pour produire les résultats les plus généraux, c'est à dire incluant les réseaux anonymes et non anonymes. Les recouvrements de graphes sont encore utilisés aujourd'hui pour étudier de nouveaux modèles de calculs. L'objectif de cet atelier est de faire le lien entre d'anciens résultats, parfois un peu oubliés, et de nouveaux modèles de calcul, et des résultats récents. Il s'agit d'un premier session d'une future série. C'est pourquoi l'accent est mis principalement sur les réseaux anonymes.Programme
Les matinées seront consacrées à des keynotes sur l'utilisation des couvertures de graphes pour les réseaux anonymes et les après-midi à des présentations de résultats récents utilisant, directement ou indirectement, les couvertures de graphes dans algorithmes distribués. Appel à témoignages : Une session spécifique sera dédiée aux témoignages concernant l’utilisation, ou la tentative d’utilisation, des revêtements de graphes. Il sera également possible de présenter des problèmes ouverts. Informations et inscription : https://coverings.lis-lab.fr Contact: coverings@lis-lab.frSeminaire : Séminaire modèles de langage - ChatGPT
09/02/2023 à 13h00
Le jeudi 09/02 à 13h, l'équipe TALEP a le plaisir d'accueillir, pour son séminaire, Géraldine Damnati de Orange Innovation.Sa présentation est intitulée : Premières évaluations et nouveaux use-cases, quelles limitations et quelles opportunités pour les Large Language Models en contexte opérationnel ?
Cette intervention sera précédée d'une introduction rapide de Benoit Favre sur les modèles et méthodes de TAL sur lesquelles repose ChatGPT. À la suite du séminaire, nous vous proposons d'avoir une discussion sur l'impact de cette technologie dans le cadre de nos enseignements.
Nous invitons l'ensemble des membres du LIS à participer à cet événement. Le séminaire aura lieu à l'amphi de l'Hexagone le jeudi 09/02 à 13h. Il sera possible d'y assister par zoom via le lien ci-dessous :
https://univ-amu-fr.zoom.us/j/86852094022?pwd=YVBvNVk0WlYwZ2hUS0VQcVozZnBVQT09
Ne manquez pas cette occasion unique de découvrir les dernières avancées en matière de technologies linguistiques !
Amicalement,
Carlos Ramisch
P.S. : ce message a été écrit à l'aide de ChatGPT, bien entendu.