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.
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.