Average-case analysis of algorithms using Kolmogorov complexity View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2000-09

AUTHORS

Tao Jiang, Ming Li, Paul M. B. Vitányi

ABSTRACT

Analyzing the average-case complexity of algorithms is a very practical but very difficult problem in computer science. In the past few years, we have demonstrated that Kolmogorov complexity is an important tool for analyzing the average-case complexity of algorithms. We have developed the incompressibility method. In this paper, several simple examples are used to further demonstrate the power and simplicity of such method. We prove bounds on the average-case number of stacks (queues) required for sorting sequential or parallel Queuesort or Stacksort. More... »

PAGES

402-408

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf02950402

DOI

http://dx.doi.org/10.1007/bf02950402

DIMENSIONS

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


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 California, Riverside", 
          "id": "https://www.grid.ac/institutes/grid.266097.c", 
          "name": [
            "Department of Computing Science, University of California, 92521, Riverside, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jiang", 
        "givenName": "Tao", 
        "id": "sg:person.015107424575.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015107424575.17"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of California, Santa Barbara", 
          "id": "https://www.grid.ac/institutes/grid.133342.4", 
          "name": [
            "Department of Computer Science, University of California, 93106, Santa Barbara, CA, USA"
          ], 
          "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 M. B.", 
        "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.1214/aop/1176996798", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009269121"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321694.321704", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013112467"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/368370.368387", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013192838"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0001-8708(77)90030-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019830529"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/355483.355488", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020534084"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1025044546", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4757-2606-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025044546", 
          "https://doi.org/10.1007/978-1-4757-2606-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4757-2606-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025044546", 
          "https://doi.org/10.1007/978-1-4757-2606-0"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2000-09", 
    "datePublishedReg": "2000-09-01", 
    "description": "Analyzing the average-case complexity of algorithms is a very practical but very difficult problem in computer science. In the past few years, we have demonstrated that Kolmogorov complexity is an important tool for analyzing the average-case complexity of algorithms. We have developed the incompressibility method. In this paper, several simple examples are used to further demonstrate the power and simplicity of such method. We prove bounds on the average-case number of stacks (queues) required for sorting sequential or parallel Queuesort or Stacksort.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf02950402", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1320078", 
        "issn": [
          "1666-6046", 
          "1666-6038"
        ], 
        "name": "Journal of Computer Science and Technology", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "5", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "15"
      }
    ], 
    "name": "Average-case analysis of algorithms using Kolmogorov complexity", 
    "pagination": "402-408", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "15f67328eca15fc39aa83c6bc3a9b2a3bfeb3c91ddbce93a6e969abfe3d8644b"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02950402"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1004609185"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02950402", 
      "https://app.dimensions.ai/details/publication/pub.1004609185"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T14:33", 
    "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/0000000373_0000000373/records_13106_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2FBF02950402"
  }
]
 

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/bf02950402'

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/bf02950402'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02950402'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02950402'


 

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

102 TRIPLES      21 PREDICATES      34 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02950402 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nde85c384cf0946de94de46a7713505a8
4 schema:citation sg:pub.10.1007/978-1-4757-2606-0
5 https://app.dimensions.ai/details/publication/pub.1025044546
6 https://doi.org/10.1016/0001-8708(77)90030-5
7 https://doi.org/10.1145/321694.321704
8 https://doi.org/10.1145/355483.355488
9 https://doi.org/10.1145/368370.368387
10 https://doi.org/10.1214/aop/1176996798
11 schema:datePublished 2000-09
12 schema:datePublishedReg 2000-09-01
13 schema:description Analyzing the average-case complexity of algorithms is a very practical but very difficult problem in computer science. In the past few years, we have demonstrated that Kolmogorov complexity is an important tool for analyzing the average-case complexity of algorithms. We have developed the incompressibility method. In this paper, several simple examples are used to further demonstrate the power and simplicity of such method. We prove bounds on the average-case number of stacks (queues) required for sorting sequential or parallel Queuesort or Stacksort.
14 schema:genre research_article
15 schema:inLanguage en
16 schema:isAccessibleForFree true
17 schema:isPartOf N18a066d1845e4586ba6cb5a5ab29fc7f
18 Naf36817a718b4db9bd9daa238da194b3
19 sg:journal.1320078
20 schema:name Average-case analysis of algorithms using Kolmogorov complexity
21 schema:pagination 402-408
22 schema:productId N9237e7fd144e4b5f8a24cf252c9c52bd
23 Nbde639a301a44780bf694cd2bdceb185
24 Nf4de3825ec764465a08620c0623babe1
25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004609185
26 https://doi.org/10.1007/bf02950402
27 schema:sdDatePublished 2019-04-11T14:33
28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
29 schema:sdPublisher Na3bd7be9aa0c473c8b16888e19a5eb52
30 schema:url http://link.springer.com/10.1007%2FBF02950402
31 sgo:license sg:explorer/license/
32 sgo:sdDataset articles
33 rdf:type schema:ScholarlyArticle
34 N18a066d1845e4586ba6cb5a5ab29fc7f schema:issueNumber 5
35 rdf:type schema:PublicationIssue
36 N9237e7fd144e4b5f8a24cf252c9c52bd schema:name doi
37 schema:value 10.1007/bf02950402
38 rdf:type schema:PropertyValue
39 N9b330c8478724284865c140f197c96b2 rdf:first sg:person.014213763741.01
40 rdf:rest rdf:nil
41 Na3bd7be9aa0c473c8b16888e19a5eb52 schema:name Springer Nature - SN SciGraph project
42 rdf:type schema:Organization
43 Na76501c583c04a0d9807bbe7e09669f9 rdf:first sg:person.0621576316.79
44 rdf:rest N9b330c8478724284865c140f197c96b2
45 Naf36817a718b4db9bd9daa238da194b3 schema:volumeNumber 15
46 rdf:type schema:PublicationVolume
47 Nbde639a301a44780bf694cd2bdceb185 schema:name readcube_id
48 schema:value 15f67328eca15fc39aa83c6bc3a9b2a3bfeb3c91ddbce93a6e969abfe3d8644b
49 rdf:type schema:PropertyValue
50 Nde85c384cf0946de94de46a7713505a8 rdf:first sg:person.015107424575.17
51 rdf:rest Na76501c583c04a0d9807bbe7e09669f9
52 Nf4de3825ec764465a08620c0623babe1 schema:name dimensions_id
53 schema:value pub.1004609185
54 rdf:type schema:PropertyValue
55 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
56 schema:name Information and Computing Sciences
57 rdf:type schema:DefinedTerm
58 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
59 schema:name Computation Theory and Mathematics
60 rdf:type schema:DefinedTerm
61 sg:journal.1320078 schema:issn 1666-6038
62 1666-6046
63 schema:name Journal of Computer Science and Technology
64 rdf:type schema:Periodical
65 sg:person.014213763741.01 schema:affiliation https://www.grid.ac/institutes/grid.7177.6
66 schema:familyName Vitányi
67 schema:givenName Paul M. B.
68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014213763741.01
69 rdf:type schema:Person
70 sg:person.015107424575.17 schema:affiliation https://www.grid.ac/institutes/grid.266097.c
71 schema:familyName Jiang
72 schema:givenName Tao
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015107424575.17
74 rdf:type schema:Person
75 sg:person.0621576316.79 schema:affiliation https://www.grid.ac/institutes/grid.133342.4
76 schema:familyName Li
77 schema:givenName Ming
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79
79 rdf:type schema:Person
80 sg:pub.10.1007/978-1-4757-2606-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025044546
81 https://doi.org/10.1007/978-1-4757-2606-0
82 rdf:type schema:CreativeWork
83 https://app.dimensions.ai/details/publication/pub.1025044546 schema:CreativeWork
84 https://doi.org/10.1016/0001-8708(77)90030-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019830529
85 rdf:type schema:CreativeWork
86 https://doi.org/10.1145/321694.321704 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013112467
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1145/355483.355488 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020534084
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1145/368370.368387 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013192838
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1214/aop/1176996798 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009269121
93 rdf:type schema:CreativeWork
94 https://www.grid.ac/institutes/grid.133342.4 schema:alternateName University of California, Santa Barbara
95 schema:name Department of Computer Science, University of California, 93106, Santa Barbara, CA, USA
96 rdf:type schema:Organization
97 https://www.grid.ac/institutes/grid.266097.c schema:alternateName University of California, Riverside
98 schema:name Department of Computing Science, University of California, 92521, Riverside, CA, USA
99 rdf:type schema:Organization
100 https://www.grid.ac/institutes/grid.7177.6 schema:alternateName University of Amsterdam
101 schema:name CWI and University of Amsterdam, Kruislaan 413, 1098 SJ, Amsterdam, The Netherlands
102 rdf:type schema:Organization
 




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


...