Agenda

Département
Langue
Date
Thématique
2025

mai

juin

  • 14:00
    15:00

    Universal Skolem Sets

    The Skolem Problem asks to determine whether a given integer linear recurrence sequence (such as the Fibonacci numbers) has a zero term. This problem, whose decidability has been open for many decades, arises across a wide range of topics in computer science, including loop termination, probabilistic model checking, weighted automata theory, and dynamical systems, amongst many others. Recently, a new approach to the Skolem Problem was initiated via the notion of a Universal Skolem Set: a set S of natural numbers with the property that it is decidable, for any given linear recurrence sequence, whether the sequence has a zero in S. I will present a survey and overview of the Skolem Problem, including lines of attack based on Universal Skolem Sets.

    This is joint work with Florian Luca, James Maynard, Armand Noubissie, and James Worrell.

    178
  • 11:00
    12:00

    Timothé Picavet (LaBRI)

    Title: Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors

    Abstract:

    We show that graphs excluding $K_{2,t}$ as a minor admit a f(t)-round 50-approximation deterministic distributed algorithm for Minimum Dominating Set. The result extends to Minimum Vertex Cover. Though fast and approximate distributed algorithms for such problems were already known for H-minor-free graphs, all of them have an approximation ratio depending on the size of H. To the best of our knowledge, this is the first example of a large non-trivial excluded minor leading to fast and constant-approximation distributed algorithms, where the ratio is independent of the size of H. A new key ingredient in the analysis of these distributed algorithms is the use of asymptotic dimension.

    The talk will be in English if there is a non-(sufficiently)-French-speaking person in the audience and in French otherwise.

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

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

    Redundancy is a central concept in gauge theory, where gauge-invariant degrees of freedom are redundantly encoded into gauge-variant quantities (in order to preserve locality). Likewise, redundancy is a hallmark of any quantum error correcting code, which redundantly encodes logical quantum information into a larger quantum system (in order to protect it against certain interactions with the environment). I will explain how this simple observation can be turned into a precise correspondence relating the formalism of quantum error correction to that of quantum gauge theory. I will focus more concretely on the well-studied family of stabilizer codes, which can be interpreted as Abelian gauge theories with gauge group a product of $\mathbb{Z}_2$. It includes repetition codes such as the elementary three-qubit code, and topological codes such as Kitaev's toric code, which I will use as illustrative examples. The notion of quantum reference frame (QRF) will provide a crucial ingredient relating structures on both sides of the correspondence. In particular, I will explain how a choice of maximal set of correctable errors on the QECC side, is equivalent to a choice of QRF on the gauge theory side. The correspondence also reveals a new duality structure among maximal correctable error sets, which can be understood as a manifestation of Pontryagin duality of Abelian groups. Based on joint work with A. Chatwin-Davies, P. Höhn, and F. M. Mele [ [ https://arxiv.org/abs/2412.15317 | https://arxiv.org/abs/2412.15317 ] ].

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

    Room 178 - unsual time!