New Applications of the Incompressibility Method

DOI10.1093/COMJNL/42.4.287MaRDI QIDQ4933948zbMATH OpenOpenAlexFDO

Authors Tao Jiang, Paul M. B. Vitányi, Ming Li

Publication date 17 January 2000

Published in The Computer Journal (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/80d3c246573e34e129311f4f546e02157c6fb781

zbMATH Keywords

incompressibility method

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• New applications of the incompressibility method. II
• Average-case analysis via incompressibility
• New applications of the incompressibility method. (Extended abstract)
• Some examples of average-case analysis by the incompressibility method
• On the paper of Pascal Schweitzer concerning similarities between incompressibility methods and the Lovász local lemma

Cited in

(5)

• Incompressibility and global inversion
• New applications of the incompressibility method. II
• Average-case analysis of quicksort and binary insertion tree height using incompressibility
• New applications of the incompressibility method. (Extended abstract)
• Some examples of average-case analysis by the incompressibility method

This page was built for publication: New Applications of the Incompressibility Method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933948)