GT et PÉC de l'équipe Combinatoire et Interactions
La petite école et le séminaire de l'équipe Combinatoire et Interactions (CI) ont lieu les lundis. Les horaires sont de de 9h30 à 10h30 pour la PÉC et de 10h45 à 11h45 pour le GT. Ils ont lieu dans la salle 076 au rez-de-chaussée du LaBRI (bâtiment A30).
Lorsque l'exposé est filmé il est retransmis via zoom
https://u-bordeaux-fr.zoom.us/j/83326403471?pwd=VLapX1qCOgASs3V8OktWtKEr8dn041.1
Meeting ID: 833 2640 3471
Passcode: 1251442
Contactez les responsables (Vincent Delecroix, Oscar Fontaine et Juliette Schabanel) si vous voulez proposer un exposé. Pour recevoir les annonces de la PÉC ou du GT, envoyez un mail à sympa[at]diff.u-bordeaux.fr avec comme objet "subscribe labri.cea-gt".
Pour l'historique des exposés précédents, voir le menu "GT CI" à droite de la page.
2025-2026
Lundi 4 mai: Guillaume Lagarde (LaBRI, Bordeaux)
Exceptionnellement en salle 178 (exposé commun avec AlgoDist)
titre: Analyzing and Leveraging the k-Sensitivity of LZ77
résumé:
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.
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|.
Lundi 11 mai: Baptiste Louf (IMB, Bordeaux)
Lundi 18 mai: Dorian Perrot (LORIA, Nancy)
Lundi 25 mai: Pentecôte
Lundi 1 juin: à saisir
Lundi 8 juin: à saisir
Lundi 15 juin: à saisir
Lundi 22 juin: à saisir
Lundi 29 juin: à saisir