Average-Case Analysis Using Kolmogorov Complexity View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1997

AUTHORS

Ming Li , Paul Vitányi

ABSTRACT

This expository paper demonstrates how to use Kolmogorov complexity to do the average-case analysis via four examples, and exhibits a surprising property of the celebrated associated universal distribution. The four examples are: average case analysis of Heapsort [17, 15], average nni-distance between two binary rooted leave-labeled trees [20], 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 [14]. We provide the proofs for the latter three items. More... »

PAGES

157-169

References to SciGraph publications

Book

TITLE

Advances in Algorithms, Languages, and Complexity

ISBN

978-1-4613-3396-8
978-1-4613-3394-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-1-4613-3394-4_7

DOI

http://dx.doi.org/10.1007/978-1-4613-3394-4_7

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1043635137


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "City University of Hong Kong, Hong Kong", 
            "University of Waterloo, Canada", 
            "Department of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ont., Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Li", 
        "givenName": "Ming", 
        "id": "sg:person.0621576316.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Amsterdam", 
          "id": "https://www.grid.ac/institutes/grid.7177.6", 
          "name": [
            "CWI and University of Amsterdam, Kruislaan 413, 1098 SJ, Amsterdam, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vit\u00e1nyi", 
        "givenName": "Paul", 
        "id": "sg:person.014213763741.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014213763741.01"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/248052.248076", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001687858"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/355588.365103", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007471015"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1012361330", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4757-3860-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012361330", 
          "https://doi.org/10.1007/978-1-4757-3860-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4757-3860-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012361330", 
          "https://doi.org/10.1007/978-1-4757-3860-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0004-3702(92)90016-q", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045821526"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0004-3702(92)90016-q", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045821526"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(92)90138-l", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052370509"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(82)90083-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053439545"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jagm.1993.1031", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053505024"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/t-c.1973.223748", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061455821"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0222012", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842415"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0405034", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062844728"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s009753979223842x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879771"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/2974642", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1070157331"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1997", 
    "datePublishedReg": "1997-01-01", 
    "description": "This expository paper demonstrates how to use Kolmogorov complexity to do the average-case analysis via four examples, and exhibits a surprising property of the celebrated associated universal distribution. The four examples are: average case analysis of Heapsort [17, 15], average nni-distance between two binary rooted leave-labeled trees [20], 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 [14]. We provide the proofs for the latter three items.", 
    "editor": [
      {
        "familyName": "Du", 
        "givenName": "Ding-Zhu", 
        "type": "Person"
      }, 
      {
        "familyName": "Ko", 
        "givenName": "Ker-I", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-1-4613-3394-4_7", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-1-4613-3396-8", 
        "978-1-4613-3394-4"
      ], 
      "name": "Advances in Algorithms, Languages, and Complexity", 
      "type": "Book"
    }, 
    "name": "Average-Case Analysis Using Kolmogorov Complexity", 
    "pagination": "157-169", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1043635137"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-1-4613-3394-4_7"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "cfd99b8df5d0f57677e0fc808380d69797333867ee5db070836de839eaf6eb86"
        ]
      }
    ], 
    "publisher": {
      "location": "Boston, MA", 
      "name": "Springer US", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-1-4613-3394-4_7", 
      "https://app.dimensions.ai/details/publication/pub.1043635137"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T09:50", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000376_0000000376/records_56158_00000002.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-1-4613-3394-4_7"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-1-4613-3394-4_7'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-1-4613-3394-4_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-1-4613-3394-4_7'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-1-4613-3394-4_7'


 

This table displays all metadata directly associated to this object as RDF triples.

121 TRIPLES      23 PREDICATES      40 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-1-4613-3394-4_7 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Na31a751fb037456597318090f4b5558c
4 schema:citation sg:pub.10.1007/978-1-4757-3860-5
5 https://app.dimensions.ai/details/publication/pub.1012361330
6 https://doi.org/10.1006/jagm.1993.1031
7 https://doi.org/10.1016/0004-3702(92)90016-q
8 https://doi.org/10.1016/0020-0190(82)90083-7
9 https://doi.org/10.1016/0020-0190(92)90138-l
10 https://doi.org/10.1109/t-c.1973.223748
11 https://doi.org/10.1137/0222012
12 https://doi.org/10.1137/0405034
13 https://doi.org/10.1137/s009753979223842x
14 https://doi.org/10.1145/248052.248076
15 https://doi.org/10.1145/355588.365103
16 https://doi.org/10.2307/2974642
17 schema:datePublished 1997
18 schema:datePublishedReg 1997-01-01
19 schema:description This expository paper demonstrates how to use Kolmogorov complexity to do the average-case analysis via four examples, and exhibits a surprising property of the celebrated associated universal distribution. The four examples are: average case analysis of Heapsort [17, 15], average nni-distance between two binary rooted leave-labeled trees [20], 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 [14]. We provide the proofs for the latter three items.
20 schema:editor N0a528ca65a914e109902a6a1bd0550da
21 schema:genre chapter
22 schema:inLanguage en
23 schema:isAccessibleForFree true
24 schema:isPartOf Nab416948fd6749e2b3f2cadf05dfbd82
25 schema:name Average-Case Analysis Using Kolmogorov Complexity
26 schema:pagination 157-169
27 schema:productId N22288be9baae4f84810a2752519883b3
28 N3487cef762fb490aa48c6c3802492b8d
29 Ncfe8aa2a9380408aaf4530a4c2123a70
30 schema:publisher N83b8ad255eb343748f74acddd59186d0
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043635137
32 https://doi.org/10.1007/978-1-4613-3394-4_7
33 schema:sdDatePublished 2019-04-16T09:50
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher N4d509aaae90d4782bb4e48ac811988e7
36 schema:url https://link.springer.com/10.1007%2F978-1-4613-3394-4_7
37 sgo:license sg:explorer/license/
38 sgo:sdDataset chapters
39 rdf:type schema:Chapter
40 N0a528ca65a914e109902a6a1bd0550da rdf:first Na0f58ee2f8c84d48b8a78a3c546bb08e
41 rdf:rest N773ec62f4d9d4604a0c8e1709f5a5abd
42 N22288be9baae4f84810a2752519883b3 schema:name readcube_id
43 schema:value cfd99b8df5d0f57677e0fc808380d69797333867ee5db070836de839eaf6eb86
44 rdf:type schema:PropertyValue
45 N3487cef762fb490aa48c6c3802492b8d schema:name dimensions_id
46 schema:value pub.1043635137
47 rdf:type schema:PropertyValue
48 N4d509aaae90d4782bb4e48ac811988e7 schema:name Springer Nature - SN SciGraph project
49 rdf:type schema:Organization
50 N773ec62f4d9d4604a0c8e1709f5a5abd rdf:first N8b52a43f31a6413bbfd1bc04150b113a
51 rdf:rest rdf:nil
52 N83b8ad255eb343748f74acddd59186d0 schema:location Boston, MA
53 schema:name Springer US
54 rdf:type schema:Organisation
55 N8b52a43f31a6413bbfd1bc04150b113a schema:familyName Ko
56 schema:givenName Ker-I
57 rdf:type schema:Person
58 Na0f58ee2f8c84d48b8a78a3c546bb08e schema:familyName Du
59 schema:givenName Ding-Zhu
60 rdf:type schema:Person
61 Na31a751fb037456597318090f4b5558c rdf:first sg:person.0621576316.79
62 rdf:rest Nd5a603a3f90c49e9be245793bee1f584
63 Nab416948fd6749e2b3f2cadf05dfbd82 schema:isbn 978-1-4613-3394-4
64 978-1-4613-3396-8
65 schema:name Advances in Algorithms, Languages, and Complexity
66 rdf:type schema:Book
67 Ncfe8aa2a9380408aaf4530a4c2123a70 schema:name doi
68 schema:value 10.1007/978-1-4613-3394-4_7
69 rdf:type schema:PropertyValue
70 Nd5a603a3f90c49e9be245793bee1f584 rdf:first sg:person.014213763741.01
71 rdf:rest rdf:nil
72 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
73 schema:name Information and Computing Sciences
74 rdf:type schema:DefinedTerm
75 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
76 schema:name Computation Theory and Mathematics
77 rdf:type schema:DefinedTerm
78 sg:person.014213763741.01 schema:affiliation https://www.grid.ac/institutes/grid.7177.6
79 schema:familyName Vitányi
80 schema:givenName Paul
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014213763741.01
82 rdf:type schema:Person
83 sg:person.0621576316.79 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
84 schema:familyName Li
85 schema:givenName Ming
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79
87 rdf:type schema:Person
88 sg:pub.10.1007/978-1-4757-3860-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012361330
89 https://doi.org/10.1007/978-1-4757-3860-5
90 rdf:type schema:CreativeWork
91 https://app.dimensions.ai/details/publication/pub.1012361330 schema:CreativeWork
92 https://doi.org/10.1006/jagm.1993.1031 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053505024
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1016/0004-3702(92)90016-q schema:sameAs https://app.dimensions.ai/details/publication/pub.1045821526
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1016/0020-0190(82)90083-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053439545
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1016/0020-0190(92)90138-l schema:sameAs https://app.dimensions.ai/details/publication/pub.1052370509
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1109/t-c.1973.223748 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061455821
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1137/0222012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842415
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1137/0405034 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844728
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1137/s009753979223842x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879771
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1145/248052.248076 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001687858
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1145/355588.365103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007471015
111 rdf:type schema:CreativeWork
112 https://doi.org/10.2307/2974642 schema:sameAs https://app.dimensions.ai/details/publication/pub.1070157331
113 rdf:type schema:CreativeWork
114 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
115 schema:name City University of Hong Kong, Hong Kong
116 Department of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ont., Canada
117 University of Waterloo, Canada
118 rdf:type schema:Organization
119 https://www.grid.ac/institutes/grid.7177.6 schema:alternateName University of Amsterdam
120 schema:name CWI and University of Amsterdam, Kruislaan 413, 1098 SJ, Amsterdam, The Netherlands
121 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...