Calendrier des animations scientifiques

Le concept d’ordinateur quantique, basé sur des qubits et l’algorithmique quantique, existe depuis près de 30 ans (Feynman 1982, Shor 1995, Grover 1996). Ces dix dernières années, de véritables machines quantiques ont été construites (allant de 5 à 5000 qubits), permettant aujourd’hui d’exécuter des programmes (Farhi 2014, Google Quantum AI 2024).

La superposition quantique des variables de décision induit un nouveau paradigme de calcul, permettant d’envisager de casser la combinatoire et ouvrant ainsi la voie à un nouveau domaine : la Recherche Opérationnelle Quantique.

Après un bref rappel des outils manipulés et de l’intuition sous-jacente, je présenterai diverses approches pour modéliser (et éventuellement résoudre ?) le problème du voyageur de commerce (Traveling Salesman Problem, TSP).

We introduce ribbon graphs, also known as topological graphs or cellularly embedded graphs, and show how delta-matroids come from ribbon graphs in the same way that matroids come from graphs. The talk will be mainly introductory and include a discussion of minors, duality and twisted duality. We show how delta-matroids allows us to count spanning quasi-trees (the ribbon graph analogue of spanning trees) and prove a matrix-tree theorem.

Ever since Macaulay introduced his famous resultant, one philosophy in
the algorithmic treatment of polynomial systems of equations has been
that problems can be solved by linearizing them in sufficiently high
degree. A major challenge, however, consists in the size of this
degree which has, for example, been shown to be doubly exponential in
the worst case for Gröbner basis computations.

In this talk, we showcase three new algorithms which permit to linearize
problems in polynomial system solving, aiming to lower the maximum degree
reached by computations with respect to the state of the art.

The first of these algorithms concerns the problem of equidimensional
decomposition. We propose a new strategy based on signature-based
Gröbner basis algorithms which reduce this problem to detecting rank
deficiencies in certain matrices. We sketch a potential future
application of this work to the problem of finding algorithms for
matrix multiplication.

The second algorithm gives a new p-adic method to compute Gröbner
bases. We highlight the resulting complexity bounds which are
quasi-linear in some output size. This is joint work with Jérémy
Berthomieu.

Finally, we showcase an algorithm in polyhedral geometry which permits
to linearize implicitization problems. We highlight advantages
compared to state-of-the-art methods and pose some questions with
respect to the resulting linear algebra problems. This is joint work
with Yulia Mukhina.

Le diagnostic des maladies rares est un défi de taille. Chaque patient porte une histoire clinique unique, souvent parsemée d’errance et d’impasse diagnostique. C’est en affrontant ces complexités lors de mon internat de médecine en génétique médicale que j’ai pris conscience du potentiel du machine learning pour transformer cette quête diagnostique en un parcours plus rapide et plus précis.

Dès mes premiers travaux, j’ai développé des algorithmes capables d’explorer les données génomiques en profondeur, réinterprétant des résultats ambigus et détectant des anomalies subtiles, telles que les variations du nombre de copies ou les disomies uniparentales. Mais le véritable tournant est venu avec PhenoGenius, un modèle conçu pour dépasser les limites des descriptions cliniques traditionnelles. En exploitant la co-occurrence des symptômes, il priorise les gènes candidats avec une précision inédite, surmontant ainsi la variabilité inhérente aux symptômes saisis par des médecins.

Depuis mon arrivée dans l’équipe Computational Regulatory Genomics, je participe à construire des méthodologies pour résoudre de nouvelles impasses diagnostiques en utilisant des algorithmes de machine learning pour interpréter les variations non-codantes de notre génome, soit 98% de notre ADN actuellement inexpliqué en routine diagnostique.

Chaque avancée, chaque modèle développé, chaque algorithme affiné s’inscrit dans une ambition plus vaste : transformer la médecine personnalisée en une réalité concrète, où l’innovation algorithmique et l’intégration des données complexes permettent aux patients de trouver des réponses diagnostiques.

Large phylogenetic trees pose a significant challenge to evolutionary inference due to computational tractability issues. This challenge has become increasingly important with the growing availability of sequence data, driven by advancements in genomics and the rising popularity of phylodynamic analyses in epidemiological studies. Deep learning in birth-death modeling has grown in popularity in recent years, particularly for addressing scalability issues (e.g., data size) that affect standard likelihood-based methods such as Maximum Likelihood and Bayesian Inference. Previous studies using convolutional neural networks have shown that empirical birth-death trees are typically more unbalanced than their simulated counterparts. This is likely due to diversification rates varying over time and across clades. Differences in selective pressures, driven by temporally and spatially varying environmental conditions, have produced multiple diversification trajectories embedded within a single phylogeny. Current approaches to deep learning in birth-death modeling rely on compact vector encoding of phylogenetic trees and have proven efficient as an alternative to whole-tree likelihood-based methods. However, they may not provide accurate predictions using empirical trees when rate heterogeneity is presumed to be high. Here, we explore the application of a new encoding language that uses local information contained in individual vectors per node, combined with the splitting of the original tree into subtrees, to estimate changes in speciation and relative extinction rates across clades and over time. We demonstrate that this approach is efficient for large trees simulated with 10,000 tips, which are subsequently divided into 500 nodes subtrees. We examine the power and accuracy of our approach using two distinct node-sampling strategies: one designed to detect discrete rate shifts across the tree and the other to identify rate shifts among clades.

Coarse graph theory is an emerging research direction that aims to describe the global structure of graphs by ignoring their local structure. In this talk, I will present an overview of this area, highlighting both recent positive and negative developments. A key focus of this talk will be the notion of quasi-isometry and conditions under which graphs are quasi-isometric to graphs with bounded treewidth.

This talk is based on some recent joint works with Rutger Campbell, Maria Chudnowsky, James Davies, Marc Distel, Meike Hatzel, Freddie Illingworth, and Rose McCarty.

The vehicle routing problem with time windows (VRPTW) is a classical problem with many applications. To improve schedules accuracy, the models may consider time dependency in travel time. The real traffic data used as input to the optimizers are often obtained by location providers that predict the travel times for specified timeframes. The predictors estimate travel time based on historical data, where uncertainties from accidents, weather conditions, and working roads, may add unpredictable delays. These providers enhance their forecasts by monitoring the live traffic and updating the travel time throughout the day.

Since routes are typically designed iin advance, updates are hard to integrate once execution starts. In this context, this work introduces the robust time-dependent VRPTW (RTDVRPTW), which uses robust optimization to handle uncertainty in travel times.

In this talk, we discuss the computational properties of RTDVRPTW under various assumptions, present exact and heuristic solution methods, and share results from real-data experiments to offer practical insights.

In secure multi-party computation (MPC), efficiency is often enhanced through the use of correlated randomness. Classical examples of correlated randomness consist of Oblivious Transfers (OT) or Oblivious Linear Evaluations (OLE). As pseudorandomness can be efficiently generated from a small amount of randomness, Boyle et al. demonstrated the feasibility of constructing pseudorandom Correlation Generators: from a small amount of random correlation, obtaining a large amount of pseudorandom correlation.

In this talk, I will mainly focus on the constructions of PCG for the OLE correlation. We will discuss the importance of programmable PCGs, their implications, and how PCGs can be built from codes. We will notably investigate how the Quasi-Abelian Syndrome Decoding Problem, introduced by Bombar et al. (Crypto 2023) as a generalization of the Quasi-Cyclic Decoding Problem, can be employed to design programmable PCGs for OLE correlations over any finite field Fq, where q > 2. Additionally, I will expose several improvements over the original constructions coming from FOLEAGE (Asiacrypt 2024).

This talk is based on joint works with Maxime Bombar, Dung Bui, Geoffroy Couteau, Alain Couvreur, and Sacha Servan-Schreibe