Agenda
mai
-
10:4511:45
ATTENTION: 10:45
Guillaume Lagarde (LaBRI)
Title: Analyzing and Leveraging the k-Sensitivity of LZ77
Abstract:
We study the sensitivity of the Lempel-Ziv 77 compression algorithm to edits, showing how modifying a string can deteriorate or improve its compression. Our first result is a tight upper bound for k edits: ∀w'∈B(w,k), we have C_{LZ77}(w') ≤ 3 C_{LZ77}(w) + 4k. This result contrasts with Lempel-Ziv 78, where a single edit can significantly deteriorate compressibility, a phenomenon known as a « one-bit catastrophe ».
We further refine this bound, focusing on the coefficient 3 in front of C_{LZ77}(w), and establish a surprising trichotomy based on the compressibility of w. More precisely we prove the following bounds:
· if C_{LZ77}(w) ≲ k^{3/2} √n, the compression may increase by up to a factor of ≈3,
· if k^{3/2} √n ≲ C_{LZ77}(w) ≲ k^{1/3} n^{2.3}, this factor is at most ≈2,
· if C_{LZ77}(w) ≳ k^{1/3} n^{2.3}, the factor is at most ≈1.F
Finally, we present an ε-approximation algorithm to pre-edit a word w with a budget of k modifications to improve its compression. In favorable scenarios, this approach yields a total compressed size reduction by up to a factor of ~3, accounting for both the LZ77 compression of the modified word and the cost of storing the edits, C_{LZ77}(w')+k log |w|.FrançaisLaBRI 178 -
10:4511:45
In this talk, I will discuss the entanglement properties of mixtures of Dicke states. These quantum states form an important subclass of bosonic states arising in the study of indistinguishable particles.
We introduce a tensor-based parametrization where the diagonal entries of these states are encoded as a symmetric tensor, enabling a direct translation between entanglement properties and well-studied convex cones of tensors. This dictionary maps separability to completely positive tensors, the PPT property to moment tensors, entanglement witnesses to copositive tensors, and decomposable witnesses to sum of squares tensors.
As corollaries of our main results, we establish that PPT entanglement exists for all multipartite systems with three qutrits or more, disproving a recent conjecture in [J. Math. Phys. 66, 022203 (2025)]. We also show that, for mixtures of Dicke states, the PPT condition with respect to the most balanced bipartition implies PPT with respect to any other bipartition. We further connect bosonic extendibility of mixtures of Dicke states to the duals of known hierarchies for non-negative polynomials, such as the ones by Reznick and Polya. We thus provide semidefinite programming relaxations for separability and entanglement testing in the Dicke subspace.
This is based on the work with Ion Nechita (CNRS, LPT Toulouse) and Clément Pellegrini (IMT Toulouse). The preprint is available at [ https://arxiv.org/abs/2602.15800 | https://arxiv.org/abs/2602.15800 ]
FrançaisLaBRI -
12:3013:00
Patrice Benoit, Chargé de la visibilité des publications scientifique - Service Transversal Soutien à la Recherche (DIRDOC) animera ce webinaire.
Comment réaliser concrètement un dépôt : étapes clés, choix de la version, respect des politiques des éditeurs.
Bonnes pratiques pour optimiser ses dépôts (métadonnées, affiliations, liens d’identifiants chercheurs) et gérer son profil auteur dans la durée.Ce format court (30 min) a pour objectif de sensibiliser aux enjeux et aux pratiques de la science ouverte, et est destinée à toute la communauté universitaire de Bordeaux, plus particulièrement les doctorantes, doctorants, chercheurs et chercheuses.
Webinaire
juin
-
14:0015:00FrançaisLaBRI