BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:62d1c3ff-cadc-49a0-b5a7-d4e97aede918
X-WR-CALNAME:GT AlgoDist — 10:45\, «Analyzing and Leveraging the k-Sensitiv
 ity of LZ77»\, Guillaume Lagarde
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20280326T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20251026T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20261025T030000
RDATE:20271031T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20260329T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20270328T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:62d1c3ff-cadc-49a0-b5a7-d4e97aede918
DTSTAMP:20260427T175019Z
CLASS:PUBLIC
DESCRIPTION:ATTENTION: 10:45\n\nGuillaume Lagarde (LaBRI)\n\nTitle: Analyzi
 ng and Leveraging the k-Sensitivity of LZ77\n\nAbstract:\n\nWe study the s
 ensitivity of the Lempel-Ziv 77 compression algorithm to edits\, showing h
 ow modifying a string can deteriorate or improve its compression. Our firs
 t 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\, whe
 re a single edit can significantly deteriorate compressibility\, a phenome
 non known as a « one-bit catastrophe ».\n           \nWe further refine th
 is bound\, focusing on the coefficient 3 in front of C_{LZ77}(w)\, and est
 ablish a surprising trichotomy based on the compressibility of w. More pre
 cisely we prove the following bounds: \n· if C_{LZ77}(w) ≲ k^{3/2} √n\, th
 e compression may increase by up to a factor of ≈3\,\n· if  k^{3/2} √n ≲ C
 _{LZ77}(w) ≲ k^{1/3} n^{2.3}\, this factor is at most  ≈2\,\n· if  C_{LZ77
 }(w) ≳ k^{1/3} n^{2.3}\, the factor is at most ≈1.\n\nF\nFinally\, we pres
 ent an ε-approximation algorithm to pre-edit a word w with a budget of k m
 odifications to improve its compression. In favorable scenarios\, this app
 roach yields a total compressed size reduction by up to a factor of ~3\, a
 ccounting for both the LZ77 compression of the modified word and the cost 
 of storing the edits\, C_{LZ77}(w')+k log |w|.\n\n\n\nhttps://algodist.lab
 ri.fr/index.php/Main/GT\n\nImport automatique depuis https://webmel.u-bord
 eaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.algo-dist.ics par sync_icals_to_
 drupal.py pour gt-algodist
DTSTART;TZID=Europe/Paris:20260504T104500
DTEND;TZID=Europe/Paris:20260504T114500
LOCATION:LaBRI 178
SEQUENCE:0
SUMMARY:GT AlgoDist — 10:45\, «Analyzing and Leveraging the k-Sensitivity o
 f LZ77»\, Guillaume Lagarde
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
