The Incompressibility Method View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2000

AUTHORS

Tao Jiang , Ming Li , Paul Vitányi

ABSTRACT

Kolmogorov complexity is a modern notion of randomness dealing with the quantity of information in individual objects; that is, pointwise randomness rather than average randomness as produced by a random source. It was proposed by A. N. Kolmogorov in 1965 to quantify the randomness of individual objects in an objective and absolute manner. This is impossible for classical probability theory. Kolmogorov complexity is known variously as ‘algorithmic information’, ‘algorithmic entropy’, ‘Kolmogorov-Chaitin complexity’, ‘descriptional complexity’, ‘shortest program length’, ‘algorithmic randomness’, and others. Using it, we developed a new mathematical proof technique, now known as the ‘incompressibility method’. The incompressibility method is a basic general technique such as the ‘pigeon hole’ argument, ‘the counting method’ or the ‘probabilistic method’. The new method has been quite successful and we present recent examples. The first example concerns a “static” problem in combinatorial geometry. From among (n 3) triangles with vertices chosen from among n points in the unit square, U, 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 (uniform distribution) then there exist positive c and C such that c/n 3 < µn < C/n 3 for all large enough n, where µn is the expectation of A. Moreover, c/n 3 More... »

PAGES

36-53

Book

TITLE

SOFSEM 2000: Theory and Practice of Informatics

ISBN

978-3-540-41348-6
978-3-540-44411-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44411-4_3

DOI

http://dx.doi.org/10.1007/3-540-44411-4_3

DIMENSIONS

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


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/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of California, Riverside", 
          "id": "https://www.grid.ac/institutes/grid.266097.c", 
          "name": [
            "Department of Computer Science, University of California, 92521\u00a0Riverside, 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": [
            "Computer Science Department, University of California, 93106\u00a0Santa 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\u00a0Amsterdam, 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.1112/jlms/s1-26.3.198", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004040638"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1112/plms/s3-25.2.193", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012844530"
        ], 
        "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.1112/jlms/s2-4.3.545", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014109523"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0001-8708(76)90100-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021597112"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(85)90158-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027436275"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(85)90158-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027436275"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/(sici)1098-2418(199701/03)10:1/2<125::aid-rsa6>3.0.co;2-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027590546"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0196-6774(80)90003-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028591447"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1112/jlms/s2-25.1.13", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041741489"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-3975(99)00184-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046418755"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(85)90042-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046924626"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1112/jlms/s2-24.3.385", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048349875"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1112/plms/s3-25.3.543", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052943864"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/2687869", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1070060308"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/2690746", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1070062424"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2000", 
    "datePublishedReg": "2000-01-01", 
    "description": "Kolmogorov complexity is a modern notion of randomness dealing with the quantity of information in individual objects; that is, pointwise randomness rather than average randomness as produced by a random source. It was proposed by A. N. Kolmogorov in 1965 to quantify the randomness of individual objects in an objective and absolute manner. This is impossible for classical probability theory. Kolmogorov complexity is known variously as \u2018algorithmic information\u2019, \u2018algorithmic entropy\u2019, \u2018Kolmogorov-Chaitin complexity\u2019, \u2018descriptional complexity\u2019, \u2018shortest program length\u2019, \u2018algorithmic randomness\u2019, and others. Using it, we developed a new mathematical proof technique, now known as the \u2018incompressibility method\u2019. The incompressibility method is a basic general technique such as the \u2018pigeon hole\u2019 argument, \u2018the counting method\u2019 or the \u2018probabilistic method\u2019. The new method has been quite successful and we present recent examples. The first example concerns a \u201cstatic\u201d problem in combinatorial geometry. From among (n 3) triangles with vertices chosen from among n points in the unit square, U, let T be the one with the smallest area, and let A be the area of T. Heilbronn\u2019s 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 (uniform distribution) then there exist positive c and C such that c/n 3 < \u00b5n < C/n 3 for all large enough n, where \u00b5n is the expectation of A. Moreover, c/n 3 
 
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-44411-4_3'

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-44411-4_3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44411-4_3'

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-44411-4_3'


 

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

140 TRIPLES      23 PREDICATES      42 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44411-4_3 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N2d326910b20747f0b81bc35a4feee035
4 schema:citation https://doi.org/10.1002/(sici)1098-2418(199701/03)10:1/2<125::aid-rsa6>3.0.co;2-x
5 https://doi.org/10.1016/0001-8708(76)90100-6
6 https://doi.org/10.1016/0012-365x(85)90158-x
7 https://doi.org/10.1016/0022-0000(85)90042-x
8 https://doi.org/10.1016/0196-6774(80)90003-6
9 https://doi.org/10.1016/s0304-3975(99)00184-x
10 https://doi.org/10.1112/jlms/s1-26.3.198
11 https://doi.org/10.1112/jlms/s2-24.3.385
12 https://doi.org/10.1112/jlms/s2-25.1.13
13 https://doi.org/10.1112/jlms/s2-4.3.545
14 https://doi.org/10.1112/plms/s3-25.2.193
15 https://doi.org/10.1112/plms/s3-25.3.543
16 https://doi.org/10.1145/368370.368387
17 https://doi.org/10.2307/2687869
18 https://doi.org/10.2307/2690746
19 schema:datePublished 2000
20 schema:datePublishedReg 2000-01-01
21 schema:description Kolmogorov complexity is a modern notion of randomness dealing with the quantity of information in individual objects; that is, pointwise randomness rather than average randomness as produced by a random source. It was proposed by A. N. Kolmogorov in 1965 to quantify the randomness of individual objects in an objective and absolute manner. This is impossible for classical probability theory. Kolmogorov complexity is known variously as ‘algorithmic information’, ‘algorithmic entropy’, ‘Kolmogorov-Chaitin complexity’, ‘descriptional complexity’, ‘shortest program length’, ‘algorithmic randomness’, and others. Using it, we developed a new mathematical proof technique, now known as the ‘incompressibility method’. The incompressibility method is a basic general technique such as the ‘pigeon hole’ argument, ‘the counting method’ or the ‘probabilistic method’. The new method has been quite successful and we present recent examples. The first example concerns a “static” problem in combinatorial geometry. From among (n 3) triangles with vertices chosen from among n points in the unit square, U, 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 (uniform distribution) then there exist positive c and C such that c/n 3 < µn < C/n 3 for all large enough n, where µn is the expectation of A. Moreover, c/n 3 <A < C/n 3 for almost all A, that is, almost all A are close to the expectation value so that we determine the area of the smallest triangle for an arrangement in “general position”. Our second example concerns a “dynamic” problem in average-case running time of algorithms. The question of a nontrivial general lower bound (or upper bound) on the average-case complexity of Shellsort has been open for about forty years. We obtain the first such lower bound.
22 schema:editor N34bbb21b43134f038be16dd074f4f02e
23 schema:genre chapter
24 schema:inLanguage en
25 schema:isAccessibleForFree false
26 schema:isPartOf N996f04f1590945f09b25949612f9ffa0
27 schema:name The Incompressibility Method
28 schema:pagination 36-53
29 schema:productId N3ce32ffc50da4ac8b093a1b786e89c4f
30 Ncd429bf3404c44c7ac7f1b70355a3a3a
31 Ndeed8db9bbb34dc9af0e2963875bd8fb
32 schema:publisher Nd17adac6581c436988204094f5c14b61
33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037108539
34 https://doi.org/10.1007/3-540-44411-4_3
35 schema:sdDatePublished 2019-04-15T11:36
36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
37 schema:sdPublisher N5655eff9a2634edebcfd255171fab32a
38 schema:url http://link.springer.com/10.1007/3-540-44411-4_3
39 sgo:license sg:explorer/license/
40 sgo:sdDataset chapters
41 rdf:type schema:Chapter
42 N1b4f9c24e96b40ce9e3e8eba65cb347b rdf:first sg:person.0621576316.79
43 rdf:rest N45c24800cf074d6e9c01b39b88fe039a
44 N2ce71ed179164bbe879d9a7773c9ebc4 schema:familyName Jeffery
45 schema:givenName Keith G.
46 rdf:type schema:Person
47 N2d326910b20747f0b81bc35a4feee035 rdf:first sg:person.015107424575.17
48 rdf:rest N1b4f9c24e96b40ce9e3e8eba65cb347b
49 N34bbb21b43134f038be16dd074f4f02e rdf:first Nc9929bfbcc984062819c6655dd583776
50 rdf:rest N98e3d296a1124fb199a6be13e4f94232
51 N3ce32ffc50da4ac8b093a1b786e89c4f schema:name doi
52 schema:value 10.1007/3-540-44411-4_3
53 rdf:type schema:PropertyValue
54 N45c24800cf074d6e9c01b39b88fe039a rdf:first sg:person.014213763741.01
55 rdf:rest rdf:nil
56 N5655eff9a2634edebcfd255171fab32a schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 N83f16c23934c4b69a062392b59a377e8 rdf:first Naa913d23f9fa40eabd7c2fe9a023486a
59 rdf:rest rdf:nil
60 N98e3d296a1124fb199a6be13e4f94232 rdf:first N2ce71ed179164bbe879d9a7773c9ebc4
61 rdf:rest N83f16c23934c4b69a062392b59a377e8
62 N996f04f1590945f09b25949612f9ffa0 schema:isbn 978-3-540-41348-6
63 978-3-540-44411-4
64 schema:name SOFSEM 2000: Theory and Practice of Informatics
65 rdf:type schema:Book
66 Naa913d23f9fa40eabd7c2fe9a023486a schema:familyName Wiedermann
67 schema:givenName Jiří
68 rdf:type schema:Person
69 Nc9929bfbcc984062819c6655dd583776 schema:familyName Hlaváč
70 schema:givenName Václav
71 rdf:type schema:Person
72 Ncd429bf3404c44c7ac7f1b70355a3a3a schema:name dimensions_id
73 schema:value pub.1037108539
74 rdf:type schema:PropertyValue
75 Nd17adac6581c436988204094f5c14b61 schema:location Berlin, Heidelberg
76 schema:name Springer Berlin Heidelberg
77 rdf:type schema:Organisation
78 Ndeed8db9bbb34dc9af0e2963875bd8fb schema:name readcube_id
79 schema:value b0c5b3d87cc524a749c99ad88f74b9da95c776be29d1934bc8dbb662e2523d68
80 rdf:type schema:PropertyValue
81 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
82 schema:name Mathematical Sciences
83 rdf:type schema:DefinedTerm
84 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
85 schema:name Pure Mathematics
86 rdf:type schema:DefinedTerm
87 sg:person.014213763741.01 schema:affiliation https://www.grid.ac/institutes/grid.7177.6
88 schema:familyName Vitányi
89 schema:givenName Paul
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014213763741.01
91 rdf:type schema:Person
92 sg:person.015107424575.17 schema:affiliation https://www.grid.ac/institutes/grid.266097.c
93 schema:familyName Jiang
94 schema:givenName Tao
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015107424575.17
96 rdf:type schema:Person
97 sg:person.0621576316.79 schema:affiliation https://www.grid.ac/institutes/grid.133342.4
98 schema:familyName Li
99 schema:givenName Ming
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79
101 rdf:type schema:Person
102 https://doi.org/10.1002/(sici)1098-2418(199701/03)10:1/2<125::aid-rsa6>3.0.co;2-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1027590546
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1016/0001-8708(76)90100-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021597112
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1016/0012-365x(85)90158-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1027436275
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1016/0022-0000(85)90042-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1046924626
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/0196-6774(80)90003-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028591447
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/s0304-3975(99)00184-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1046418755
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1112/jlms/s1-26.3.198 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004040638
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1112/jlms/s2-24.3.385 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048349875
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1112/jlms/s2-25.1.13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041741489
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1112/jlms/s2-4.3.545 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014109523
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1112/plms/s3-25.2.193 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012844530
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1112/plms/s3-25.3.543 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052943864
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1145/368370.368387 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013192838
127 rdf:type schema:CreativeWork
128 https://doi.org/10.2307/2687869 schema:sameAs https://app.dimensions.ai/details/publication/pub.1070060308
129 rdf:type schema:CreativeWork
130 https://doi.org/10.2307/2690746 schema:sameAs https://app.dimensions.ai/details/publication/pub.1070062424
131 rdf:type schema:CreativeWork
132 https://www.grid.ac/institutes/grid.133342.4 schema:alternateName University of California, Santa Barbara
133 schema:name Computer Science Department, University of California, 93106 Santa Barbara, CA, USA
134 rdf:type schema:Organization
135 https://www.grid.ac/institutes/grid.266097.c schema:alternateName University of California, Riverside
136 schema:name Department of Computer Science, University of California, 92521 Riverside, CA, USA
137 rdf:type schema:Organization
138 https://www.grid.ac/institutes/grid.7177.6 schema:alternateName University of Amsterdam
139 schema:name CWI and University of Amsterdam, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands
140 rdf:type schema:Organization
 




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


...