Agenda

Département
Langue
Date
Thématique
2024

décembre

  • 10:45
    11:45

    Having query access to a bounded degree directed graph in the unidirectional model means that querying a vertex v reveals the list of vertices u such that there is a directed edge from v to u. Quantum algorithms can make these queries in superposition. In this model, we consider the problem of property testing k-star-freeness, i.e. the algorithm has to distinguish, with high probability, between (1) the graph having no vertex with at least k incoming edges (k-star); (2) the graph being “far” from this, meaning that one has to delete a constant fraction of the edges to make the graph free from k-stars.

    In the classical unidirectional model the problem of testing k-star-freeness (and more generally k-source-subgraph-freeness) is almost maximally hard for large (but constant) k, i.e. the query complexity is almost linear in the number of vertices. We give a quantum algorithm to show that this problem has almost quadratic advantage in the quantum setting. Moreover, we prove that this advantage is nearly tight, by proving a quantum lower bound using the method of dual polynomials on an intermediate problem that is a previously unstudied, property testing version of the k-collision problem.

    Joint work with Simon Apers, Frédéric Magniez and Sayantan Sen.

    https://combalgo.labri.fr/pmwiki.php/Groupe/Info-Quantique

    Room 178
  • 12:45
    13:45

    Mélanie Prague interviendra dans le cadre des séminaires Numerics.

    Amphi LaBRI
  • 15:30
    18:30

    Résumé : Cette thèse présente de nouvelles formes et de nouveaux outils pour communiquer des données et créer des visualisations. Avec la prolifération des pratiques basées sur les données, les visualisations de données sont essentielles pour l'analyse des données ainsi que pour la communication à diverses parties prenantes. Cependant, la conception de la visualisation et de la communication des données est rendue difficile par la complexité des phénomènes du monde réel représentés par les données, les ensembles de données eux-mêmes et l'expertise des analystes et des communicateurs. C'est pourquoi, dans cette thèse, je cherche à répondre aux questions suivantes : comment aider les gens à présenter et à expliquer des données complexes ? et comment les aider à créer et à utiliser la visualisation de manière efficace ? Je résume les recherches portant sur trois défis clés respectifs dans ce contexte : (i) la création et l'étude de formes de narration et de communication basées sur les données (bandes dessinées, tableaux de bord, atlas de visualisation, articles de visualisation, dataGIFs) ; (ii) la conception et la mise en œuvre d'outils pour concevoir, créer et utiliser la visualisation (création de bandes dessinées interactives, visites semi-automatiques de données, grammaire de visualisation de réseaux) ; et (iii) l'enseignement des compétences liées à la connaissance et à la conception de la visualisation (défis rencontrés dans l'exploration des réseaux, défis dans l'enseignement de la visualisation, explication automatique des schémas visuels). Je conclurai par une discussion sur les orientations futures de la recherche concernant les nouvelles formes de narration, la création et la conception de la visualisation, et l'enseignement de la visualisation.

    Biographie : Benjamin est chercheur à l'Institut national de recherche en sciences et technologies du numérique (Inria) au sein de l'équipe Bivwac, à Bordeaux. Il est également professeur associé (Reader) à la School of Informatics de l'Université d'Edimbourg où il a fondé le groupe de recherche VisHub. Les recherches de Benjamin portent sur des visualisations de données, des interfaces et des outils plus efficaces et efficients pour l'analyse de données, la communication et l'éducation. Il collabore régulièrement avec des chercheurs en sciences sociales, des historiens, des biologistes, des chercheurs en paix et des organisations publiques. Benjamin a été nommé nouveau chercheur important par la conférence VIS de l'IEEE (2021) et jeune chercheur d'Eurographics (2019). Son doctorat a reçu la mention honorable du prix de la meilleure thèse du VGTC (2014). https://vishub.net/bach
     

    Amphi LaBRI
  • 12:45
    13:45

    Les Jeux olympiques de Paris 2024 ont représenté un défi unique pour intégrer les principes du numérique responsable dans un événement d’une telle ampleur. Avec des millions d’utilisateurs, des infrastructures techniques massives, et une temporalité fixe, l’objectif était d’allier performance, inclusivité et durabilité dans un cadre marqué par des contraintes opérationnelles strictes. Cette expérience montre que, même dans un événement aussi complexe que les JO, il est possible d’intégrer des principes de numérique responsable. Cependant, elle rappelle également que la transformation nécessite un alignement fort entre les ambitions environnementales et les contraintes d’organisation.

    Salle 76
  • 13:00
    14:00

    Decision problems for finitely generated groups: overview and perspectives

    I will present a historical account of the study of computability on finitely generated groups.
    I will first survey some classical results that concern the study finitely presented groups.
    We will then see that a recent theorem of Groves and Wilton introduces a completely new perspective on the subject: the ‘correct’ description of groups that need to be used to study decision problems was not the one that was studied. It is as though we had plenty of results about functions on the left computable reals and far fewer about functions defined on the computable reals.
    I will discuss some research directions which follow from the Groves-Wilton theorem.

    Salle 76
  • 11:00
    12:00

    Taïssir Marcé (LaBRI)

    Title: How to wake-up robots in a graph? (in French)

    Comment réveiller les robots dans un graphe ?

    Abstract:

    On se demande comment réveiller un ensemble de robots positionné dans l'espace : Initialement, seul un robot est réveillé. Pour réveiller un robot endormi, il faut qu'un robot éveillé s'y déplace physiquement.
    Le problème d’optimisation émanant consiste alors à déterminer dans quel ordre réveiller les robots pour minimiser le temps total de réveil.
    Dans cet exposé, on considère le problème de réveil de robot dans les espaces métriques définits par des graphes : les robots sont initialement positionnés sur des sommets du graphes et se déplacent uniquement le long des arêtes.
    On présente un algorithme pour approcher le temps de réveil optimal (16.8-approximation).
    Dans un second temps, on présente une version distribuée du problème de réveil de robot.

    https://algodist.labri.fr/index.php/Main/GT

    LaBRI salle 178 - lien visio https://webconf.u-bordeaux.fr/b/arn-4tr-7gp