January 3, Tuesday
12:00 – 13:00
(In) Compressibility of NP-hard problems
Computer Science seminar
Lecturer : Danny Hermelin
Affiliation : Max-Plank Institute for Informatics, Germany
Location : 202/37
Host : Dr. Michal Ziv-Ukelson
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.