Guillaume Lagarde (IRIF, Paris Diderot)

Les algorithmes de Lempel-Ziv désignent une famille d’algorithmes de compression sans perte qui sont utilisés dans de nombreux contextes de l’informatique (gzip, gif, etc). Pourtant, la stabilité de l’un deux (LZ’78) est encore mal établie. Vers la fin des années 90s, Jack Lutz popularise la question suivante, connue sous le nom de « one-bit catastrophe » : « étant donné un mot compressible, est-il possible de le rendre incompressible en ne changeant qu’un seul bit ? ». Nous montrons qu’une telle catastrophe est en effet possible. Plus précisément, en donnant des bornes optimales sur la variation de la taille de la compression, nous montrons qu’un mot « très compressible » restera toujours compressible après modification d’un bit, mais que certains mots « peu compressibles » deviennent en effet incompressibles.

Travail en commun avec Sylvain Perifel.