47 citations · 103 across the 12 of their papers we have counts for
12 papers
Information Distance
Charles H. Bennett, Peter Gacs, Ming Li +2
While Kolmogorov complexity is the accepted absolute measure of information content in an individual finite object, a similarly absolute notion is needed for the information distan…
Sharpening Occam's Razor
Ming Li, John Tromp, Paul Vitanyi
We provide a new representation-independent formulation of Occam's razor theorem, based on Kolmogorov complexity. This new formulation allows us to: (i) Obtain better sample comple…
Kolmogorov Random Graphs and the Incompressibility Method
Harry Buhrman, Ming Li, John Tromp +1
We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressib…
A New Approach to Formal Language Theory by Kolmogorov Complexity
Ming Li, Paul Vitanyi
We present a new approach to formal language theory using Kolmogorov complexity. The main results presented here are an alternative for pumping lemma(s), a new characterization for…
A Lower Bound on the Average-Case Complexity of Shellsort
Tao Jiang, Ming Li, Paul Vitanyi
We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a -pass Shellsort for any incremental…
The Average-Case Area of Heilbronn-Type Triangles
Tao Jiang, Ming Li, Paul Vitanyi
From among triangles with vertices chosen from points in the unit square, let be the one with the smallest area, and let be the area of . Heilbronn'…