Evènement pour le groupe Séminaire Méthodes Formelles

Date 2020-01-14  07:00-07:00
TitreLempel-Ziv: A "one-bit catastrophe" but not a tragedy 
RésuméLZ'78 is a famous and very simple lossless data compression algorithm published by Abraham Lempel and Jacob Ziv in 1978. Although widely used in practise, we know little about its stability. The one-bit catastrophe question, introduced by Jack Lutz in the late 90s, asks whether an infinite word compressible by LZ'78 can become incompressible by adding a single bit in front of it. Our main result is to answer that question positively. We also give tight bounds on the maximal possible variation between the compression ratio of a finite word and its perturbation (when one bit is added in front of it), showing that to get a "catastrophe", the initial word needs already to be close to the threshold of incompressibility. This is a joint work with Sylvain Perifel. 
OrateurGuillaume Lagarde 

Aucun document lié à cet événement.

Retour à l'index