Agenda
décembre
-
13:0014:00
Contribution à la conception et la fabrication de robots souples pneumatiques
Loïc Mosser
https://u-bordeaux-fr.zoom.us/j/83483228567Remote -
14:0017:00Amphi du LaBRI
-
10:4511: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.
Room 178 -
12:4513:45
Mélanie Prague interviendra dans le cadre des séminaires Numerics.
Amphi LaBRI -
12:4513: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:0014: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:0012: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.LaBRI salle 178 - lien visio https://webconf.u-bordeaux.fr/b/arn-4tr-7gp