Ming Li
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Ming Li has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
- Paul Vitanyi
CWI University of Amsterdam
5 shared publications - Tao Jiang
University of California
4 shared publications - Bin Ma
University of Western Ontario
1 shared publication - Huandong Sun
Bioinformatics Laboratory, Department of Computer Science, University of California, Santa Barbara, CA 93106, USA
1 shared publication - Lusheng Wang
City University of Hong Kong
1 shared publication Qiong Gao
1 shared publication
Latest Publications
- Open Access
A Lower Bound on the Average-Case Complexity of Shellsort
We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a $p$-pass Shellsort for any incremental sequence is $\Omega (pn^{1 + 1/p})$ for every $p$. The proof method is an incompressibility argument based on Kolmogorov complexity. Using similar techniques, the average-case complexity of several other sorting algorithms is analyzed.Open AccessA Lower Bound on the Average-Case Complexity of Shellsort
We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a $p$-pass Shellsort for any incremental sequence is $\Omega (pn^{1 + 1/p})$ for every $p$. The proof method is an incompressibility argument based on Kolmogorov complexity. Using similar techniques, the average-case complexity of several other sorting algorithms is analyzed. - Open Access
The Average-Case Area of Heilbronn-Type Triangles
From among $ {n \choose 3}$ triangles with vertices chosen from $n$ points in the unit square, let $T$ be the one with the smallest area, and let $A$ be the area of $T$. Heilbronn's triangle problem asks for the maximum value assumed by $A$ over all choices of $n$ points. We consider the average-case: If the $n$ points are chosen independently and at random (with a uniform distribution), then there exist positive constants $c$ and $C$ such that $c/n^3 < \mu_n < C/n^3$ for all large enough values of $n$, where $\mu_n$ is the expectation of $A$. Moreover, $c/n^3 < A < C/n^3$, with probability close to one. Our proof uses the incompressibility method based on Kolmogorov complexity; it actually determines the area of the smallest triangle for an arrangement in ``general position.''Open AccessThe Average-Case Area of Heilbronn-Type Triangles
From among $ {n \choose 3}$ triangles with vertices chosen from $n$ points in the unit square, let $T$ be the one with the smallest area, and let $A$ be the area of $T$. Heilbronn's triangle problem asks for the maximum value assumed by $A$ over all choices of $n$ points. We consider the average-case: If the $n$ points are chosen independently and at random (with a uniform distribution), then there exist positive constants $c$ and $C$ such that $c/n^3 < \mu_n < C/n^3$ for all large enough values of $n$, where $\mu_n$ is the expectation of $A$. Moreover, $c/n^3 < A < C/n^3$, with probability close to one. Our proof uses the incompressibility method based on Kolmogorov complexity; it actually determines the area of the smallest triangle for an arrangement in ``general position.'' - 23 April 2003
- Published by Elsevier in Computer Methods and Programs in Biomedicine
- Vol. 71 (1) , 85-90
molvie: an interactive visualization environment for molecular structures
- 23 April 2003
- Published by Elsevier in Computer Methods and Programs in Biomedicine
- Vol. 71 (1) , 85-90
molvie: an interactive visualization environment for molecular structures
- 1 August 2002
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 65 (1) , 73-96
Finding Similar Regions in Many Sequences
- 1 August 2002
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 65 (1) , 73-96
Finding Similar Regions in Many Sequences
- 8 February 2002
- Published by Wiley in Random Structures & Algorithms
- Vol. 20 (2) , 206-219
The average-case area of Heilbronn-type triangles*
- 8 February 2002
- Published by Wiley in Random Structures & Algorithms
- Vol. 20 (2) , 206-219
The average-case area of Heilbronn-type triangles*
- 1 September 2000
- Published by Springer Nature in Journal of Computer Science and Technology
- Vol. 15 (5) , 402-408
Average-case analysis of algorithms using Kolmogorov complexity
- 1 September 2000
- Published by Springer Nature in Journal of Computer Science and Technology
- Vol. 15 (5) , 402-408
Average-case analysis of algorithms using Kolmogorov complexity
- Open Access
Applying MDL to Learning Best Model Granularity
The Minimum Description Length (MDL) principle is solidly based on a provably ideal method of inference using Kolmogorov complexity. We test how the theory behaves in practice on a general problem in model selection: that of learning the best model granularity. The performance of a model depends critically on the granularity, for example the choice of precision of the parameters. Too high precision generally involves modeling of accidental noise and too low precision may lead to confusion of models that should be distinguished. This precision is often determined ad hoc. In MDL the best model is the one that most compresses a two-part code of the data set: this embodies ``Occam's Razor.'' In two quite different experimental settings the theoretical value determined using MDL coincides with the best value found experimentally. In the first experiment the task is to recognize isolated handwritten characters in one subject's handwriting, irrespective of size and orientation. Based on a new modification of elastic matching, using multiple prototypes per character, the optimal prediction rate is predicted for the learned parameter (length of sampling interval) considered most likely by MDL, which is shown to coincide with the best value found experimentally. In the second experiment the task is to model a robot arm with two degrees of freedom using a three layer feed-forward neural network where we need to determine the number of nodes in the hidden layer giving best modeling performance. The optimal model (the one that extrapolizes best on unseen examples) is predicted for the number of nodes in the hidden layer considered most likely by MDL, which again is found to coincide with the best value found experimentally.
Open AccessApplying MDL to Learning Best Model Granularity
The Minimum Description Length (MDL) principle is solidly based on a provably ideal method of inference using Kolmogorov complexity. We test how the theory behaves in practice on a general problem in model selection: that of learning the best model granularity. The performance of a model depends critically on the granularity, for example the choice of precision of the parameters. Too high precision generally involves modeling of accidental noise and too low precision may lead to confusion of models that should be distinguished. This precision is often determined ad hoc. In MDL the best model is the one that most compresses a two-part code of the data set: this embodies ``Occam's Razor.'' In two quite different experimental settings the theoretical value determined using MDL coincides with the best value found experimentally. In the first experiment the task is to recognize isolated handwritten characters in one subject's handwriting, irrespective of size and orientation. Based on a new modification of elastic matching, using multiple prototypes per character, the optimal prediction rate is predicted for the learned parameter (length of sampling interval) considered most likely by MDL, which is shown to coincide with the best value found experimentally. In the second experiment the task is to model a robot arm with two degrees of freedom using a three layer feed-forward neural network where we need to determine the number of nodes in the hidden layer giving best modeling performance. The optimal model (the one that extrapolizes best on unseen examples) is predicted for the number of nodes in the hidden layer considered most likely by MDL, which again is found to coincide with the best value found experimentally.