New Applications of the Incompressibility Method (Extended Abstract) View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2002-01-18

AUTHORS

Harry Buhrman , Paul Vitányi , Tao Jiang , Ming Li

ABSTRACT

The incompressibility method is an elementary yet powerful proof technique based on Kolmogorov complexity [13]. We show that it is particularly suited to obtain average-case computational complexity lower bounds. Such lower bounds have been difficult to obtain in the past by other methods. In this paper we present four new results and also give four new proofs of known results to demonstrate the power and elegance of the new method. More... »

PAGES

220-229

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-66224-2
978-3-540-48523-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-48523-6_19

DOI

http://dx.doi.org/10.1007/3-540-48523-6_19

DIMENSIONS

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


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": "Centrum Wiskunde and Informatica", 
          "id": "https://www.grid.ac/institutes/grid.6054.7", 
          "name": [
            "CWI, Kruislaan 413, 1098, Amsterdam, SJ, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Buhrman", 
        "givenName": "Harry", 
        "id": "sg:person.0773331206.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0773331206.93"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Centrum Wiskunde and Informatica", 
          "id": "https://www.grid.ac/institutes/grid.6054.7", 
          "name": [
            "CWI, Kruislaan 413, 1098, Amsterdam, SJ, 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"
      }, 
      {
        "affiliation": {
          "alternateName": "McMaster University", 
          "id": "https://www.grid.ac/institutes/grid.25073.33", 
          "name": [
            "Dept of Computing and Software, McMaster University, L8S 4K1, Hamilton, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jiang", 
        "givenName": "Tao", 
        "id": "sg:person.011617335564.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011617335564.48"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Dept of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, 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"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0096-3003(93)90037-f", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000935809"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-49543-6_24", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001200935", 
          "https://doi.org/10.1007/3-540-49543-6_24"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01275672", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001435218", 
          "https://doi.org/10.1007/bf01275672"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01275672", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001435218", 
          "https://doi.org/10.1007/bf01275672"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(93)90135-v", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008298359"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0019-9958(73)90228-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012027700"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0036198", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017820476", 
          "https://doi.org/10.1007/bfb0036198"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/28395.28396", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018137247"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0097-3165(94)90064-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019398427"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1022523966", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-0-8176-4729-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022523966", 
          "https://doi.org/10.1007/978-0-8176-4729-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-0-8176-4729-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022523966", 
          "https://doi.org/10.1007/978-0-8176-4729-2"
        ], 
        "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"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539794275914", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879972"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4064/fm-6-1-9-20", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091683240"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/1107", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098905482"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2002-01-18", 
    "datePublishedReg": "2002-01-18", 
    "description": "The incompressibility method is an elementary yet powerful proof technique based on Kolmogorov complexity [13]. We show that it is particularly suited to obtain average-case computational complexity lower bounds. Such lower bounds have been difficult to obtain in the past by other methods. In this paper we present four new results and also give four new proofs of known results to demonstrate the power and elegance of the new method.", 
    "editor": [
      {
        "familyName": "Wiedermann", 
        "givenName": "Ji\u0159\u00ed", 
        "type": "Person"
      }, 
      {
        "familyName": "van Emde Boas", 
        "givenName": "Peter", 
        "type": "Person"
      }, 
      {
        "familyName": "Nielsen", 
        "givenName": "Mogens", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-48523-6_19", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66224-2", 
        "978-3-540-48523-0"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "name": "New Applications of the Incompressibility Method (Extended Abstract)", 
    "pagination": "220-229", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-48523-6_19"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "cb913f8f41031b610e1f38faeafa4e5785cba73bdb63927847f242993117a752"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1042735573"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-48523-6_19", 
      "https://app.dimensions.ai/details/publication/pub.1042735573"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:47", 
    "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/0000000347_0000000347/records_89814_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F3-540-48523-6_19"
  }
]
 

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/3-540-48523-6_19'

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/3-540-48523-6_19'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48523-6_19'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-48523-6_19'


 

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

150 TRIPLES      23 PREDICATES      41 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-48523-6_19 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nf24f0a454d104505802809640019b2d7
4 schema:citation sg:pub.10.1007/3-540-49543-6_24
5 sg:pub.10.1007/978-0-8176-4729-2
6 sg:pub.10.1007/978-1-4757-2606-0
7 sg:pub.10.1007/bf01275672
8 sg:pub.10.1007/bfb0036198
9 https://app.dimensions.ai/details/publication/pub.1022523966
10 https://app.dimensions.ai/details/publication/pub.1025044546
11 https://doi.org/10.1016/0020-0190(93)90135-v
12 https://doi.org/10.1016/0096-3003(93)90037-f
13 https://doi.org/10.1016/0097-3165(94)90064-7
14 https://doi.org/10.1016/s0019-9958(73)90228-3
15 https://doi.org/10.1137/s0097539794275914
16 https://doi.org/10.1142/1107
17 https://doi.org/10.1145/28395.28396
18 https://doi.org/10.4064/fm-6-1-9-20
19 schema:datePublished 2002-01-18
20 schema:datePublishedReg 2002-01-18
21 schema:description The incompressibility method is an elementary yet powerful proof technique based on Kolmogorov complexity [13]. We show that it is particularly suited to obtain average-case computational complexity lower bounds. Such lower bounds have been difficult to obtain in the past by other methods. In this paper we present four new results and also give four new proofs of known results to demonstrate the power and elegance of the new method.
22 schema:editor N2302e6c4c9e04c29ad629fa93a44fa7a
23 schema:genre chapter
24 schema:inLanguage en
25 schema:isAccessibleForFree true
26 schema:isPartOf Nf897a039742149a18f2eab4dbd6eed5f
27 schema:name New Applications of the Incompressibility Method (Extended Abstract)
28 schema:pagination 220-229
29 schema:productId N4fbd7ea43e05467e9bbb1b0d776c4f9b
30 Nd07cbe53e81649a49024bef398958cf5
31 Nfcaa0167107d42039a613cca5470dde8
32 schema:publisher N3f72a49adf544dc1878c2cd0b2aaba14
33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042735573
34 https://doi.org/10.1007/3-540-48523-6_19
35 schema:sdDatePublished 2019-04-16T05:47
36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
37 schema:sdPublisher N6b795e3c042549198c2f9f1df6ba6219
38 schema:url https://link.springer.com/10.1007%2F3-540-48523-6_19
39 sgo:license sg:explorer/license/
40 sgo:sdDataset chapters
41 rdf:type schema:Chapter
42 N2302e6c4c9e04c29ad629fa93a44fa7a rdf:first N23499801ad94430597a6fb2baf260cfa
43 rdf:rest Nd6925bb1c25e402480481bc128af38c6
44 N23499801ad94430597a6fb2baf260cfa schema:familyName Wiedermann
45 schema:givenName Jiří
46 rdf:type schema:Person
47 N2b4c05b18d2b44b38193c01dc81f2c83 rdf:first sg:person.014213763741.01
48 rdf:rest N40674ea5d12d48e1bc477e9be60bc277
49 N3f72a49adf544dc1878c2cd0b2aaba14 schema:location Berlin, Heidelberg
50 schema:name Springer Berlin Heidelberg
51 rdf:type schema:Organisation
52 N40674ea5d12d48e1bc477e9be60bc277 rdf:first sg:person.011617335564.48
53 rdf:rest N4096a46a3e6446938ce7352b2adc9841
54 N4096a46a3e6446938ce7352b2adc9841 rdf:first sg:person.0621576316.79
55 rdf:rest rdf:nil
56 N43fbfe0f373c4b52a19e40999be55e10 schema:familyName van Emde Boas
57 schema:givenName Peter
58 rdf:type schema:Person
59 N4fbd7ea43e05467e9bbb1b0d776c4f9b schema:name dimensions_id
60 schema:value pub.1042735573
61 rdf:type schema:PropertyValue
62 N6b795e3c042549198c2f9f1df6ba6219 schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 Nd07cbe53e81649a49024bef398958cf5 schema:name doi
65 schema:value 10.1007/3-540-48523-6_19
66 rdf:type schema:PropertyValue
67 Nd6925bb1c25e402480481bc128af38c6 rdf:first N43fbfe0f373c4b52a19e40999be55e10
68 rdf:rest Ne30c4d428abe4b3f93c36e448f69f6a5
69 Ne30c4d428abe4b3f93c36e448f69f6a5 rdf:first Nf7fe3e6c8f08479babca5b27651564dc
70 rdf:rest rdf:nil
71 Nf24f0a454d104505802809640019b2d7 rdf:first sg:person.0773331206.93
72 rdf:rest N2b4c05b18d2b44b38193c01dc81f2c83
73 Nf7fe3e6c8f08479babca5b27651564dc schema:familyName Nielsen
74 schema:givenName Mogens
75 rdf:type schema:Person
76 Nf897a039742149a18f2eab4dbd6eed5f schema:isbn 978-3-540-48523-0
77 978-3-540-66224-2
78 schema:name Automata, Languages and Programming
79 rdf:type schema:Book
80 Nfcaa0167107d42039a613cca5470dde8 schema:name readcube_id
81 schema:value cb913f8f41031b610e1f38faeafa4e5785cba73bdb63927847f242993117a752
82 rdf:type schema:PropertyValue
83 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
84 schema:name Information and Computing Sciences
85 rdf:type schema:DefinedTerm
86 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
87 schema:name Computation Theory and Mathematics
88 rdf:type schema:DefinedTerm
89 sg:person.011617335564.48 schema:affiliation https://www.grid.ac/institutes/grid.25073.33
90 schema:familyName Jiang
91 schema:givenName Tao
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011617335564.48
93 rdf:type schema:Person
94 sg:person.014213763741.01 schema:affiliation https://www.grid.ac/institutes/grid.6054.7
95 schema:familyName Vitányi
96 schema:givenName Paul
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014213763741.01
98 rdf:type schema:Person
99 sg:person.0621576316.79 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
100 schema:familyName Li
101 schema:givenName Ming
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79
103 rdf:type schema:Person
104 sg:person.0773331206.93 schema:affiliation https://www.grid.ac/institutes/grid.6054.7
105 schema:familyName Buhrman
106 schema:givenName Harry
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0773331206.93
108 rdf:type schema:Person
109 sg:pub.10.1007/3-540-49543-6_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001200935
110 https://doi.org/10.1007/3-540-49543-6_24
111 rdf:type schema:CreativeWork
112 sg:pub.10.1007/978-0-8176-4729-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022523966
113 https://doi.org/10.1007/978-0-8176-4729-2
114 rdf:type schema:CreativeWork
115 sg:pub.10.1007/978-1-4757-2606-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025044546
116 https://doi.org/10.1007/978-1-4757-2606-0
117 rdf:type schema:CreativeWork
118 sg:pub.10.1007/bf01275672 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001435218
119 https://doi.org/10.1007/bf01275672
120 rdf:type schema:CreativeWork
121 sg:pub.10.1007/bfb0036198 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017820476
122 https://doi.org/10.1007/bfb0036198
123 rdf:type schema:CreativeWork
124 https://app.dimensions.ai/details/publication/pub.1022523966 schema:CreativeWork
125 https://app.dimensions.ai/details/publication/pub.1025044546 schema:CreativeWork
126 https://doi.org/10.1016/0020-0190(93)90135-v schema:sameAs https://app.dimensions.ai/details/publication/pub.1008298359
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1016/0096-3003(93)90037-f schema:sameAs https://app.dimensions.ai/details/publication/pub.1000935809
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1016/0097-3165(94)90064-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019398427
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1016/s0019-9958(73)90228-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012027700
133 rdf:type schema:CreativeWork
134 https://doi.org/10.1137/s0097539794275914 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879972
135 rdf:type schema:CreativeWork
136 https://doi.org/10.1142/1107 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098905482
137 rdf:type schema:CreativeWork
138 https://doi.org/10.1145/28395.28396 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018137247
139 rdf:type schema:CreativeWork
140 https://doi.org/10.4064/fm-6-1-9-20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091683240
141 rdf:type schema:CreativeWork
142 https://www.grid.ac/institutes/grid.25073.33 schema:alternateName McMaster University
143 schema:name Dept of Computing and Software, McMaster University, L8S 4K1, Hamilton, Ontario, Canada
144 rdf:type schema:Organization
145 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
146 schema:name Dept of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada
147 rdf:type schema:Organization
148 https://www.grid.ac/institutes/grid.6054.7 schema:alternateName Centrum Wiskunde and Informatica
149 schema:name CWI, Kruislaan 413, 1098, Amsterdam, SJ, The Netherlands
150 rdf:type schema:Organization
 




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


...