Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: (In) Compressibility of NP-hard Problems
event speaker icon
Danny Hermelin (Max-Planck Institut Informatik, Saarbrucken, Germany)
event date icon
Wednesday, 21.12.2011, 12:30
event location icon
Taub 337
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.