Events
The Taub Faculty of Computer Science Events and Talks
Danny Hermelin (Max-Planck Institut Informatik, Saarbrucken, Germany)
Wednesday, 21.12.2011, 12:30
A compression algorithm for a computation problem is a
polynomial-time algorithm that compresses instances of the given problem
into equivalent instances. The performance of the compression is naturally
measured with respect to its worst-case output size. While NP-hard
problems cannot have compression algorithms with non-trivial performance
guarantees in terms of the original input size (assuming NP is not in P),
some NP-hard problems have surprisingly good compressions when performance
is measured in terms of the input solution size. In this talk we discuss
some recently developed lower bounds for the compressibility of NP-hard
problems when the latter measure is used.