Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Short lists for shortest descriptions in short time
Teutsch J. Computational Complexity23 (4):565-583,2014.Type:Article
Date Reviewed: Mar 3 2015

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.

Reviewer:  M. Zimand Review #: CR143215 (1506-0488)
1) Bauwens, B.; Makhlin, A.; Vereshchagin, N.; Zimand, M. Short lists with short programs in short time. In Proceedings of 28th IEEE Conference on Computational Complexity. IEEE, 2013, 98–108.
Bookmark and Share
 
Complexity Measures (D.2.8 ... )
 
 
Approximation (G.1.2 )
 
 
Discrete Mathematics (G.2 )
 
 
Mathematical Software (G.4 )
 
Would you recommend this review?
yes
no
Other reviews under "Complexity Measures": Date
Software complexity
Zuse H., Walter de Gruyter & Co., Hawthorne, NJ, 1991. Type: Book (9780899256405)
Jul 1 1992
Software complexity metric sensitivity to program structuring rules
Evangelist W. Journal of Systems and Software 3(3): 231-243, 1983. Type: Article
Feb 1 1985
An empirical study of software metrics
Li H., Cheung W. IEEE Transactions on Software Engineering SE-13(6): 697-708, 1987. Type: Article
Mar 1 1988
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy