New applications of the incompressibility method. II

DOI10.1016/S0304-3975(99)00184-XzbMath0943.68083MaRDI QIDQ1978700

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

Publication date: 4 June 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Kolmogorov complexityaverage-case analysis of algorithmsincompressibility method

Mathematics Subject Classification ID

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

Related Items (5)

A characterization of average case communication complexity ⋮ Average-case analysis of quicksort and binary insertion tree height using incompressibility ⋮ Individual communication complexity ⋮ Constraints placed on random sequences by their compressibility ⋮ Kolmogorov complexity and combinatorial methods in communication complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mathematics for the Analysis of Algorithms.
• Determining the majority
• Matrix multiplication via arithmetic progressions
• On computing majority by comparisons
• A note on the number of \(N\)-bit strings with maximum complexity
• Kolmogorov complexity arguments in combinatorics
• The Average-Case Complexity of Determining the Majority
• Communication Complexity
• New Applications of the Incompressibility Method
• A fast expected time algorithm for Boolean matrix multiplication and transitive closure

This page was built for publication: New applications of the incompressibility method. II