New applications of the incompressibility method: Part II

Authors
Buhrman, H Jiang, T Li, M Vitanyi, P
Citation
H. Buhrman et al., New applications of the incompressibility method: Part II, THEOR COMP, 235(1), 2000, pp. 59-70
Citations number
13
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
235
Issue
1
Year of publication
2000
Pages
59 - 70
Database
ISI
SICI code
0304-3975(20000317)235:1<59:NAOTIM>2.0.ZU;2-Y
Abstract
The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas (Li and Vitanyi, An Introducti on to Kolmogorov Complexity and its Applications, Springer, New York, 1997) . To further demonstrate its power and elegance we exhibit new simple proof s using the incompressibility method. (C) 2000 Elsevier Science B.V. All ri ghts reserved.