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.
Seminar
Lempel-Ziv: a 'one-bit catastrophe' but not a tragedy
- Date
- 16.04.2019, 11:00
- Place
- Pavillon des Jardins
- Speaker
- 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.