Agenda
janvier
-
13:0014:00
TBA
FrançaisLaBRI, salle 178 -
10:3018:00
10:00 - 10:30: Welcome Coffee
10:30 - 11:15 (Opening Talk): Matthieu Saubanère (CNRS & LOMA), Quantum Krylov algorithms for the many electrons problem
11:15 - 11:40: Sacha Cerf (ENS), Introducing differential geometric tools to study quantum correlations
11:40 - 12:05: Shashaank Khanna (LIS), Closing the problem of which causal structures of up to six total nodes have a classical–quantum gap
12:05 - 12:30: Idris Delsol (ENS & Inria Lyon), Computational aspects of the trace norm contraction coefficient
12:30 - 13:45: Lunch Break
13:45 - 14:10: Rémi Di Guardia (IRIF), Semantics and types for quantum Bayesian networks
14:10 - 14:35: Thomas Perez (Inria Saclay), Categorical aspects of fermionic systems and application to fermionic computation rewrites
14:35 - 15:00: Thomas Vinet (Inria Nancy), Resource-aware hybrid quantum programming with general recursion and quantum control
15:00 - 15:25: Kathleen Barsse (LORIA), A quantum programming language for coherent control
15:25 - 16:00: Coffee Break
16:00 - 16:25: Mathias Boucher (Inria Rennes), Almost improving quantum lattice sieving
16:25 - 16:50: Aurel Pichollet-Mugnier (Inria Rennes), Quantum truncated differential attacks using convolutions
16:50 - 17:15: Agathe Blanvillain (Inria Paris), The quantum decoding problem: tight achievability bounds and application to Regev’s reduction
17:15 - 17:40: Bruno Costa Alves Freire (Inria Paris), Quantum Maxwell decoder for CSS codes
17:40 - 18:00: Business Meeting of the GT IQFrançaisAmphi -
09:0017:30
9:00 - 9:30: Welcome Coffee
9:30 - 10:15 (Opening Talk): Marc Baboulin (Inria & Université Paris-Saclay), Toward quantum-accelerated high-performance computing
10:15 - 10:40: Silvina Caino Lores (Inria Rennes), TBA
10:40 - 11:05: Océane Koska (Eviden & Université Paris-Saclay), From NISQ to hybrid computing
11:05 - 11:30: Coffee Break
11:30 - 11:55: Rafael Ferreira da Silva (Oak Ridge National Laboratory), Enabling quantum-HPC convergence for future scientific workflows
11:55 - 12:20: Elise Fressart (Thalès & École Polytechnique), Adaptive mesh refinement quantum algorithm for Maxwell’s equations
12:20 - 12:40: Jules Duhamel (EPFL & SNCF), Quantum algorithms for train crew scheduling optimization
12:40 - 14:00: Lunch Break
14:00 - 14:25: Bo Yang (LIP6), Verifiable blind observable estimation
14:25 - 14:50: Pierre Botteron (ENS & Inria Lyon), Quantum unclonable cryptography: does the unclonable bit exist?
14:50 - 15:15: Denis Rochette (Inria Saclay), Optimal untelegraphable encryption and implications for uncloneable encryption
15:15 - 15:45: Coffee Break
15:45 - 16:10: Joseph Cunningham (LaBRI), Poisson-distributed discrete adiabatic dynamics
16:10 - 16:35: Rachel Roux (MBDA), Investigating the use of the discrete quantum walk to solve combinatorial optimization problems
16:35 - 17:00: Xiaoyu Sun (LIS), On quantum perceptron learning via quantum search
17:00 - 17:25: Benjamin Mathieu-Bloise (IRIF), Complexity of computations on simplicial complexes in quantum logspaceFrançaisAmphi -
14:0015:00
In 1943, Hadwiger conjectured that every k-chromatic graph has a K_k-minor. While the cases k = 5 and k = 6 have been shown to be equivalent to the Four Colour Theorem, respectively by Wagner, and in seminal work by Robertson, Seymour and Thomas, the cases k at least 7 remain open. We show that any 7-chromatic graph has as a minor the complete graph K_7 with two adjacent edges removed, by extending work of Kawarabayashi and Toft and by proving a new edge-extremal bound. This improves Jakobsen’s result with two arbitrary edges removed.
Joint work with Sergey Norin.
(Agnes Totschnig) [MIT]
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .FrançaisLaBRI/178 -
11:0012:00
Mikaël Rabie (IRIF)
Title: An introduction to the SLEEPING model
Abstract:
In distributed computing, one classical model is the LOCAL model: agents (or processors) are on the vertices of a graph, and need to communicate synchronously to solve a problem, such as coloring, maximal independent set, or matching. In particular, the goal is to provide a fast algorithm (usually polylogarithmic) for those problems. Those algorithms make each processor run during the whole computation. However, one might wonder whether it is necessary to have all processors running all the time simultaneously. To save energy, we can let processors ‘‘sleep’’ when they do not need to communicate with their neighbors. In this talk, I will introduce the SLEEPING model, with the new notion of awake complexity. In particular, I will focus on coloring problems and trade-offs between the number of awake rounds per processor and the total number of rounds.
FrançaisLaBRI 178 -
14:0015:00
Résumé : Cette présentation porte sur l’usage des ontologies comme outils de modélisation pour la gestion et l’exploitation des connaissances dans des systèmes complexes. Elle introduit les ontologies et met en évidence leur articulation avec des approches d’IA statistique et hybride afin de renforcer la cohérence, l’interprétabilité et la robustesse des modèles. Les travaux présentés sont illustrés par des applications dans les domaines de la mobilité, des systèmes ferroviaires et des systèmes industriels, où les ontologies jouent un rôle central pour la modélisation sémantique, la détection de situations complexes et l’aide à la décision.
FrançaisLaBRI -
11:0012:00FrançaisLaBRI 178
février
-
11:0012:00
Jonathan Narboni
Title: Lower Bound for Constant-Size Local Certification
Abstract:
Given a network property or a data structure, a local certification is a labeling that allows to efficiently check that the property is satisfied, or that the structure is correct. The quality of a certification is measured by the size of its labels: the smaller, the better. This notion plays a central role in self-stabilization, because the size of the certification is a lower bound (and often an upper bound) on the memory needed for silent self-stabilizing construction of distributed data structures.
When it comes to the size of the certification labels, one can identify 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.
The main contribution of this paper is the first non-trivial lower bound for this low regime. More precisely, we show that by using certification on just one bit (a binary certification), one cannot certify k-colorability for k≥3. To do so, we develop a new technique, based on the notion of score, and both local symmetry arguments and a global parity argument. We hope that this technique will be useful for establishing stronger results.
We complement this result with an upper bound for a related problem, illustrating that in some cases one can do better than the natural upper bound.
FrançaisLaBRI 178