A lower bound for randomized algebraic decision trees View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1996-12

AUTHORS

Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky

ABSTRACT

We prove the firstnontrivial (andsuperlinear) lower bounds on the depth ofrandomized algebraic decision trees (with two-sided error) for problems being finite unions of hyperplanes and intersections of halfspaces, solving a long standing open problem. As an application, among other things, we derive, for the first time, an Ω(n2)randomized lower bound for theKnapsack Problem, and an Ω(n logn)randomized lower bound for theElement Distinctness Problem which were previously known only for deterministic algebraic decision trees. It is worth noting that for the languages being finite unions of hyperplanes our proof method yields also a new elementary lower bound technique for deterministic algebraic decision trees without making use of Milnor's bound on Betti number of algebraic varieties. More... »

PAGES

357-375

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/17", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology and Cognitive Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "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/1702", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Cognitive Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science and Mathematics, Penn State University, University Park", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Dept. of Computer Science and Mathematics, Penn State University, University Park"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Grigoriev", 
        "givenName": "Dima", 
        "id": "sg:person.015253401573.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015253401573.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Bonn, 53117, Bonn", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science, University of Bonn, 53117, Bonn"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Heinz Nixdorf Institute and Computer Science Department, University of Paderborn, 33098, Paderborn", 
          "id": "http://www.grid.ac/institutes/grid.5659.f", 
          "name": [
            "Heinz Nixdorf Institute and Computer Science Department, University of Paderborn, 33098, Paderborn"
          ], 
          "type": "Organization"
        }, 
        "familyName": "auf der Heide", 
        "givenName": "Friedhelm Meyer", 
        "id": "sg:person.010426206747.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010426206747.34"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Smolensky", 
        "givenName": "Roman", 
        "id": "sg:person.010707603504.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010707603504.52"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-642-61568-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049996833", 
          "https://doi.org/10.1007/978-3-642-61568-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02770873", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039356318", 
          "https://doi.org/10.1007/bf02770873"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1996-12", 
    "datePublishedReg": "1996-12-01", 
    "description": "We prove the firstnontrivial (andsuperlinear) lower bounds on the depth ofrandomized algebraic decision trees (with two-sided error) for problems being finite unions of hyperplanes and intersections of halfspaces, solving a long standing open problem. As an application, among other things, we derive, for the first time, an \u03a9(n2)randomized lower bound for theKnapsack Problem, and an \u03a9(n logn)randomized lower bound for theElement Distinctness Problem which were previously known only for deterministic algebraic decision trees. It is worth noting that for the languages being finite unions of hyperplanes our proof method yields also a new elementary lower bound technique for deterministic algebraic decision trees without making use of Milnor's bound on Betti number of algebraic varieties.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01270387", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136224", 
        "issn": [
          "1016-3328", 
          "1420-8954"
        ], 
        "name": "computational complexity", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "6"
      }
    ], 
    "keywords": [
      "algebraic decision trees", 
      "finite union", 
      "algebraic varieties", 
      "Betti numbers", 
      "lower bounds", 
      "open problem", 
      "method yields", 
      "intersections of halfspaces", 
      "distinctness problem", 
      "hyperplane", 
      "problem", 
      "Milnor", 
      "bounds", 
      "halfspace", 
      "decision tree", 
      "applications", 
      "intersection", 
      "technique", 
      "trees", 
      "number", 
      "first time", 
      "time", 
      "variety", 
      "depth", 
      "use", 
      "things", 
      "Union", 
      "language", 
      "yield"
    ], 
    "name": "A lower bound for randomized algebraic decision trees", 
    "pagination": "357-375", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1000203451"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01270387"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01270387", 
      "https://app.dimensions.ai/details/publication/pub.1000203451"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-12-01T06:20", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/article/article_264.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01270387"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

132 TRIPLES      21 PREDICATES      59 URIs      46 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01270387 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 anzsrc-for:0802
4 anzsrc-for:17
5 anzsrc-for:1702
6 schema:author Nf0866867415642929712a66dcb486bca
7 schema:citation sg:pub.10.1007/978-3-642-61568-9
8 sg:pub.10.1007/bf02770873
9 schema:datePublished 1996-12
10 schema:datePublishedReg 1996-12-01
11 schema:description We prove the firstnontrivial (andsuperlinear) lower bounds on the depth ofrandomized algebraic decision trees (with two-sided error) for problems being finite unions of hyperplanes and intersections of halfspaces, solving a long standing open problem. As an application, among other things, we derive, for the first time, an Ω(n2)randomized lower bound for theKnapsack Problem, and an Ω(n logn)randomized lower bound for theElement Distinctness Problem which were previously known only for deterministic algebraic decision trees. It is worth noting that for the languages being finite unions of hyperplanes our proof method yields also a new elementary lower bound technique for deterministic algebraic decision trees without making use of Milnor's bound on Betti number of algebraic varieties.
12 schema:genre article
13 schema:isAccessibleForFree false
14 schema:isPartOf N92fa45b6af1c4b95a9d7455e74b17702
15 Nf59332f3494544a2a4b2c03935d6f9f1
16 sg:journal.1136224
17 schema:keywords Betti numbers
18 Milnor
19 Union
20 algebraic decision trees
21 algebraic varieties
22 applications
23 bounds
24 decision tree
25 depth
26 distinctness problem
27 finite union
28 first time
29 halfspace
30 hyperplane
31 intersection
32 intersections of halfspaces
33 language
34 lower bounds
35 method yields
36 number
37 open problem
38 problem
39 technique
40 things
41 time
42 trees
43 use
44 variety
45 yield
46 schema:name A lower bound for randomized algebraic decision trees
47 schema:pagination 357-375
48 schema:productId N2fea8c0e557340a188baf71f3ab336da
49 N74effbb578b6494995a8ac9906662e2a
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000203451
51 https://doi.org/10.1007/bf01270387
52 schema:sdDatePublished 2022-12-01T06:20
53 schema:sdLicense https://scigraph.springernature.com/explorer/license/
54 schema:sdPublisher N37d5b8dbf3d34923bad453e23dd28371
55 schema:url https://doi.org/10.1007/bf01270387
56 sgo:license sg:explorer/license/
57 sgo:sdDataset articles
58 rdf:type schema:ScholarlyArticle
59 N2fea8c0e557340a188baf71f3ab336da schema:name dimensions_id
60 schema:value pub.1000203451
61 rdf:type schema:PropertyValue
62 N37d5b8dbf3d34923bad453e23dd28371 schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 N601750ef1c2b43318e4389117f9811d6 rdf:first sg:person.010426206747.34
65 rdf:rest N64da894b0dfb46b08d4785736c5a8b3c
66 N64da894b0dfb46b08d4785736c5a8b3c rdf:first sg:person.010707603504.52
67 rdf:rest rdf:nil
68 N74effbb578b6494995a8ac9906662e2a schema:name doi
69 schema:value 10.1007/bf01270387
70 rdf:type schema:PropertyValue
71 N92fa45b6af1c4b95a9d7455e74b17702 schema:volumeNumber 6
72 rdf:type schema:PublicationVolume
73 Nf0866867415642929712a66dcb486bca rdf:first sg:person.015253401573.30
74 rdf:rest Nf68a5cf041f043dd876ee887bed7a574
75 Nf59332f3494544a2a4b2c03935d6f9f1 schema:issueNumber 4
76 rdf:type schema:PublicationIssue
77 Nf68a5cf041f043dd876ee887bed7a574 rdf:first sg:person.011636042271.02
78 rdf:rest N601750ef1c2b43318e4389117f9811d6
79 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
80 schema:name Information and Computing Sciences
81 rdf:type schema:DefinedTerm
82 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
83 schema:name Artificial Intelligence and Image Processing
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
86 schema:name Computation Theory and Mathematics
87 rdf:type schema:DefinedTerm
88 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
89 schema:name Psychology and Cognitive Sciences
90 rdf:type schema:DefinedTerm
91 anzsrc-for:1702 schema:inDefinedTermSet anzsrc-for:
92 schema:name Cognitive Sciences
93 rdf:type schema:DefinedTerm
94 sg:journal.1136224 schema:issn 1016-3328
95 1420-8954
96 schema:name computational complexity
97 schema:publisher Springer Nature
98 rdf:type schema:Periodical
99 sg:person.010426206747.34 schema:affiliation grid-institutes:grid.5659.f
100 schema:familyName auf der Heide
101 schema:givenName Friedhelm Meyer
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010426206747.34
103 rdf:type schema:Person
104 sg:person.010707603504.52 schema:familyName Smolensky
105 schema:givenName Roman
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010707603504.52
107 rdf:type schema:Person
108 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
109 schema:familyName Karpinski
110 schema:givenName Marek
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
112 rdf:type schema:Person
113 sg:person.015253401573.30 schema:affiliation grid-institutes:grid.29857.31
114 schema:familyName Grigoriev
115 schema:givenName Dima
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015253401573.30
117 rdf:type schema:Person
118 sg:pub.10.1007/978-3-642-61568-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049996833
119 https://doi.org/10.1007/978-3-642-61568-9
120 rdf:type schema:CreativeWork
121 sg:pub.10.1007/bf02770873 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039356318
122 https://doi.org/10.1007/bf02770873
123 rdf:type schema:CreativeWork
124 grid-institutes:grid.10388.32 schema:alternateName Dept. of Computer Science, University of Bonn, 53117, Bonn
125 schema:name Dept. of Computer Science, University of Bonn, 53117, Bonn
126 rdf:type schema:Organization
127 grid-institutes:grid.29857.31 schema:alternateName Dept. of Computer Science and Mathematics, Penn State University, University Park
128 schema:name Dept. of Computer Science and Mathematics, Penn State University, University Park
129 rdf:type schema:Organization
130 grid-institutes:grid.5659.f schema:alternateName Heinz Nixdorf Institute and Computer Science Department, University of Paderborn, 33098, Paderborn
131 schema:name Heinz Nixdorf Institute and Computer Science Department, University of Paderborn, 33098, Paderborn
132 rdf:type schema:Organization
 




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


...