Average-case analysis via incompressibility

DOI10.1007/BFB0036170MaRDI QIDQ5055919zbMATH OpenFDO

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

Publication date 9 December 2022

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0036170

zbMATH Keywords

average-case analysisKolmogorov complexitylonge common subsequencerandom graphuniversal distribution

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 1008511
• Average-case analysis of algorithms using Kolmogorov complexity
• scientific article; zbMATH DE number 1408350
• scientific article; zbMATH DE number 2079851
• scientific article; zbMATH DE number 1405647

Cites work

• A note on some tree similarity measures
• Addition in \(\log_{2} n+O(1)\) steps on average. A simple analysis
• An Efron-Stein inequality for nonsymmetric statistics
• Average case complexity under the universal distribution equals worst- case complexity
• How to Add Fast--on Average
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• Longest common subsequences of two random sequences
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Optimal routing tables
• Short Encodings of Evolving Structures
• Some New Results on Average Worst Case Carry
• The Analysis of Heapsort
• The Complexity of Malign Measures
• Theory and algorithms for plan merging

Cited in

(6)

• Addition in \(\log_{2} n+O(1)\) steps on average. A simple analysis
• Optimal representation in average using Kolmogorov complexity
• Average-case analysis of algorithms using Kolmogorov complexity
• scientific article; zbMATH DE number 2079851 (Why is no real title available?)
• New Applications of the Incompressibility Method
• scientific article; zbMATH DE number 1408350 (Why is no real title available?)

Describes a project that uses

Uses Software

• heapsort

This page was built for publication: Average-case analysis via incompressibility

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