Average-case analysis via incompressibility

Ming Li; Paul Vitaˆnyi

doi:10.1007/BFb0036170

Average-case analysis via incompressibility

Ming Li
, Paul Vitaˆnyi

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

We will demonstrate how to use Kolmogorov complexity to do the average-case analysis via some examples. These examples include: longest common subsequence problem and shortest common supersequence problem [9, 11], problems in computational geometry [14], average case analysis of Heapsort [19, 17], average nni-distance between two binary rooted leave-labeled trees [23], compact routing in computer networks [3], average-case analysis of an adder algorithm [4], The property is that the average-case complexity of any algorithm whatsoever equals its worst-case complexity if the inputs are distributed according to the Universal Distribution [16]. © Springer-Verlag Berlin Heidelberg 1997.

Original language	English
Title of host publication	Fundamentals of Computation Theory - 11th International Symposium, FCT 1997, Proceedings
Publisher	Springer Verlag
Pages	38-50
Volume	1279
ISBN (Print)	3540633863, 9783540633860
DOIs	https://doi.org/10.1007/BFb0036170
Publication status	Published - 1997
Externally published	Yes
Event	11th International Symposium on Fundamentals of Computation Theory, FCT 1997 - Krakow, Poland Duration: 1 Sept 1997 → 3 Sept 1997

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1279
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th International Symposium on Fundamentals of Computation Theory, FCT 1997
Place	Poland
City	Krakow
Period	1/09/97 → 3/09/97

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Access Output

10.1007/BFb0036170

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Li, M., & Vitaˆnyi, P. (1997). Average-case analysis via incompressibility. In Fundamentals of Computation Theory - 11th International Symposium, FCT 1997, Proceedings (Vol. 1279, pp. 38-50). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1279). Springer Verlag. https://doi.org/10.1007/BFb0036170

@inproceedings{676be2eace8d441d812c50cb810701fb,

title = "Average-case analysis via incompressibility",

abstract = "We will demonstrate how to use Kolmogorov complexity to do the average-case analysis via some examples. These examples include: longest common subsequence problem and shortest common supersequence problem [9, 11], problems in computational geometry [14], average case analysis of Heapsort [19, 17], average nni-distance between two binary rooted leave-labeled trees [23], compact routing in computer networks [3], average-case analysis of an adder algorithm [4], The property is that the average-case complexity of any algorithm whatsoever equals its worst-case complexity if the inputs are distributed according to the Universal Distribution [16]. {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.",

author = "Ming Li and Paul Vitaˆnyi",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].; 11th International Symposium on Fundamentals of Computation Theory, FCT 1997 ; Conference date: 01-09-1997 Through 03-09-1997",

year = "1997",

doi = "10.1007/BFb0036170",

language = "English",

isbn = "3540633863",

volume = "1279",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "38--50",

booktitle = "Fundamentals of Computation Theory - 11th International Symposium, FCT 1997, Proceedings",

address = "Germany",

}

Li, M & Vitaˆnyi, P 1997, Average-case analysis via incompressibility. in Fundamentals of Computation Theory - 11th International Symposium, FCT 1997, Proceedings. vol. 1279, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1279, Springer Verlag, pp. 38-50, 11th International Symposium on Fundamentals of Computation Theory, FCT 1997, Krakow, Poland, 1/09/97. https://doi.org/10.1007/BFb0036170

Average-case analysis via incompressibility. / Li, Ming; Vitaˆnyi, Paul.
Fundamentals of Computation Theory - 11th International Symposium, FCT 1997, Proceedings. Vol. 1279 Springer Verlag, 1997. p. 38-50 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1279).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Average-case analysis via incompressibility

AU - Li, Ming

AU - Vitaˆnyi, Paul

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 1997

Y1 - 1997

N2 - We will demonstrate how to use Kolmogorov complexity to do the average-case analysis via some examples. These examples include: longest common subsequence problem and shortest common supersequence problem [9, 11], problems in computational geometry [14], average case analysis of Heapsort [19, 17], average nni-distance between two binary rooted leave-labeled trees [23], compact routing in computer networks [3], average-case analysis of an adder algorithm [4], The property is that the average-case complexity of any algorithm whatsoever equals its worst-case complexity if the inputs are distributed according to the Universal Distribution [16]. © Springer-Verlag Berlin Heidelberg 1997.

AB - We will demonstrate how to use Kolmogorov complexity to do the average-case analysis via some examples. These examples include: longest common subsequence problem and shortest common supersequence problem [9, 11], problems in computational geometry [14], average case analysis of Heapsort [19, 17], average nni-distance between two binary rooted leave-labeled trees [23], compact routing in computer networks [3], average-case analysis of an adder algorithm [4], The property is that the average-case complexity of any algorithm whatsoever equals its worst-case complexity if the inputs are distributed according to the Universal Distribution [16]. © Springer-Verlag Berlin Heidelberg 1997.

UR - http://www.scopus.com/inward/record.url?scp=84958777034&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84958777034&origin=recordpage

U2 - 10.1007/BFb0036170

DO - 10.1007/BFb0036170

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 3540633863

SN - 9783540633860

VL - 1279

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 38

EP - 50

BT - Fundamentals of Computation Theory - 11th International Symposium, FCT 1997, Proceedings

PB - Springer Verlag

T2 - 11th International Symposium on Fundamentals of Computation Theory, FCT 1997

Y2 - 1 September 1997 through 3 September 1997

ER -

Average-case analysis via incompressibility

Abstract

Publication series

Conference

Bibliographical note

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this