GT et PÉC de l'équipe Combinatoire et Interactions

The Combinatoire et Interactions seminar runs every Monday from 10h45 to 11h45. There is also a reserved schedule for a "mini-school" from 9h30 to 10h30. Both events happen in room 076 on the ground floor of LaBRI (building A30).
When a talk is recored it is available (live and recorded) at
https://u-bordeaux-fr.zoom.us/j/83326403471?pwd=VLapX1qCOgASs3V8OktWtKEr8dn041.1
Meeting ID: 833 2640 3471
Passcode: 1251442
Contact the secretaries (Vincent Delecroix, Oscar Fontaine and Juliette Schabanel) if you want to propose a talk or to receive announcements.
For the list of previous talks, look at the menu "GT CI" on the right side of this 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


Français English

Group

Events

Talks

* previous years

Resources

edit SideBar