LSV Seminar

The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.

The seminar is open to public and does not require any form of registration.


Lempel-Ziv: a 'one-bit catastrophe' but not a tragedy

16.04.2019, 11:00
Pavillon des Jardins
Sylvain Perifel (IRIF)

The robustness of the famous compression algorithm of Lempel and Ziv is still not well understood: in particular, until now it was unknown whether the addition of one bit in front of a compressible word could make it incompressible. This talk will answer that question, advertised by Jack Lutz under the name 'one-bit catastrophe' and which has been around since at least 1998. We will show that a 'well' compressible word remains compressible when a bit is added in front of it, but some 'few' compressible words indeed become incompressible. This is a joint work with Guillaume Lagarde.

About LSV