אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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.