New applications of the incompressibility method. II

DOI10.1016/S0304-3975(99)00184-XzbMATH Open0943.68083MaRDI QIDQ1978700FDOQ1978700

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

Publication date: 4 June 2000

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

Recommendations

• New Applications of the Incompressibility Method
• Publication:4938627
• scientific article; zbMATH DE number 1408350
• scientific article; zbMATH DE number 2079851
• On the paper of Pascal Schweitzer concerning similarities between incompressibility methods and the Lovász local lemma

zbMATH Keywords

Kolmogorov complexityaverage-case analysis of algorithmsincompressibility method

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Kolmogorov complexity and combinatorial methods in communication complexity
• A characterization of average case communication complexity
• New Applications of the Incompressibility Method
• Constraints placed on random sequences by their compressibility
• Title not available (Why is that?)
• Individual communication complexity
• Average-case analysis of quicksort and binary insertion tree height using incompressibility
• Title not available (Why is that?)

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

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