Compressing a string to its shortest description (in the sense of Kolmogorov complexity) cannot be done effectively. This paper belongs to a recent research line that investigates the list approximability of the problem, namely whether it is possible to effectively construct a short list guaranteed to contain a short description.
The main result states that, quite surprisingly, it is possible to compute in polynomial time a list that contains a description of the input string whose length is additively within only a constant overhead from the shortest possible length. This improves a previous result of Bauwens et al. [1] in which the overhead is O(log n). The proof uses pseudorandomness tools such as effective expanders and dispersers.
I recommend this paper; it makes a new, solid contribution to a problem of great interest. The intended audience includes researchers in computational complexity, algorithmic information theory, information theory, and computability.