6 papers
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…
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'…
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…
New Applications of the Incompressibility Method: Part I
Tao Jiang, Ming Li, Paul Vitanyi
The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas. To further demonstrate its power and elegance we exhibit ne…
New Applications of the Incompressibility Method: Part II
Harry Buhrman, Tao Jiang, Ming Li +1
The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas. To further demonstrate its power and elegance we exhibit ne…