An exponential lower bound on the size of algebraic decision trees for Max View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1998-12

AUTHORS

D. Grigoriev, M. Karpinski, A.C. Yao

ABSTRACT

. We prove an exponential lower bound on the size of any fixed degree algebraic decision tree for solving MAX, the problem of finding the maximum of n real numbers. This complements the n— 1 lower bound of [Rabin (1972)] on the depth of algebraic decision trees for this problem. The proof in fact gives an exponential lower bound on the size of the polyhedral decision problem MAX= for testing whether the j-th number is the maximum among a list of n real numbers. Previously, except for linear decision trees, no nontrivial lower bounds on the size of algebraic decision trees for any familiar problems are known. We also establish an interesting connection between our lower bound and the maximum number of minimal cutsets for any rank-d hypergraph on n vertices. More... »

PAGES

193-203

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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, USA, e-mail: dima@cse.psu.edu, US", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Dept. of Computer Science and Mathematics, Penn State University, University Park, USA, e-mail: dima@cse.psu.edu, US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Grigoriev", 
        "givenName": "D.", 
        "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, D-53117 Bonn, e-mail: marek@cs.uni-bonn.de, DE", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science, University of Bonn, D-53117 Bonn, e-mail: marek@cs.uni-bonn.de, DE"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "M.", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, Princeton University, Princeton, New Jersey 08544, USA, e-mail: yao@cs.princeton.edu, US", 
          "id": "http://www.grid.ac/institutes/grid.16750.35", 
          "name": [
            "Dept. of Computer Science, Princeton University, Princeton, New Jersey 08544, USA, e-mail: yao@cs.princeton.edu, US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yao", 
        "givenName": "A.C.", 
        "id": "sg:person.010320662413.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010320662413.19"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1998-12", 
    "datePublishedReg": "1998-12-01", 
    "description": "Abstract. We prove an exponential lower bound on the size of any fixed degree algebraic decision tree for solving MAX, the problem of finding the maximum of n real numbers. This complements the n\u2014 1 lower bound of [Rabin (1972)] on the depth of algebraic decision trees for this problem. The proof in fact gives an exponential lower bound on the size of the polyhedral decision problem MAX= for testing whether the j-th number is the maximum among a list of n real numbers. Previously, except for linear decision trees, no nontrivial lower bounds on the size of algebraic decision trees for any familiar problems are known. We also establish an interesting connection between our lower bound and the maximum number of minimal cutsets for any rank-d hypergraph on n vertices.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s000370050010", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136224", 
        "issn": [
          "1016-3328", 
          "1420-8954"
        ], 
        "name": "computational complexity", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "7"
      }
    ], 
    "keywords": [
      "algebraic decision trees", 
      "real numbers", 
      "nontrivial lower bounds", 
      "lower bounds", 
      "interesting connections", 
      "minimal cutsets", 
      "n vertices", 
      "linear decision trees", 
      "decision problem", 
      "maximum number", 
      "problem", 
      "bounds", 
      "familiar problem", 
      "cutsets", 
      "decision tree", 
      "vertices", 
      "number", 
      "proof", 
      "maximum", 
      "max", 
      "size", 
      "trees", 
      "connection", 
      "fact", 
      "depth", 
      "list"
    ], 
    "name": "An exponential lower bound on the size of algebraic decision trees for Max", 
    "pagination": "193-203", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1000098639"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s000370050010"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s000370050010", 
      "https://app.dimensions.ai/details/publication/pub.1000098639"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-11-24T20:48", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_286.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s000370050010"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

115 TRIPLES      20 PREDICATES      54 URIs      43 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s000370050010 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 anzsrc-for:0802
4 anzsrc-for:17
5 anzsrc-for:1702
6 schema:author N8b566c779ca84f78afedc7cb8837a49e
7 schema:datePublished 1998-12
8 schema:datePublishedReg 1998-12-01
9 schema:description Abstract. We prove an exponential lower bound on the size of any fixed degree algebraic decision tree for solving MAX, the problem of finding the maximum of n real numbers. This complements the n— 1 lower bound of [Rabin (1972)] on the depth of algebraic decision trees for this problem. The proof in fact gives an exponential lower bound on the size of the polyhedral decision problem MAX= for testing whether the j-th number is the maximum among a list of n real numbers. Previously, except for linear decision trees, no nontrivial lower bounds on the size of algebraic decision trees for any familiar problems are known. We also establish an interesting connection between our lower bound and the maximum number of minimal cutsets for any rank-d hypergraph on n vertices.
10 schema:genre article
11 schema:isAccessibleForFree true
12 schema:isPartOf N569e05a896cf438ea31195ca3b4a60d8
13 N83e13e8eca9a4f2aa1468bb5f69536bf
14 sg:journal.1136224
15 schema:keywords algebraic decision trees
16 bounds
17 connection
18 cutsets
19 decision problem
20 decision tree
21 depth
22 fact
23 familiar problem
24 interesting connections
25 linear decision trees
26 list
27 lower bounds
28 max
29 maximum
30 maximum number
31 minimal cutsets
32 n vertices
33 nontrivial lower bounds
34 number
35 problem
36 proof
37 real numbers
38 size
39 trees
40 vertices
41 schema:name An exponential lower bound on the size of algebraic decision trees for Max
42 schema:pagination 193-203
43 schema:productId N08d88f13397d47c8ae53103d561acd6f
44 Na0b1879e929f486da0acd8176611686e
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000098639
46 https://doi.org/10.1007/s000370050010
47 schema:sdDatePublished 2022-11-24T20:48
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher N4c53ddb1c42c41a2875fdd489ac6bf23
50 schema:url https://doi.org/10.1007/s000370050010
51 sgo:license sg:explorer/license/
52 sgo:sdDataset articles
53 rdf:type schema:ScholarlyArticle
54 N08d88f13397d47c8ae53103d561acd6f schema:name dimensions_id
55 schema:value pub.1000098639
56 rdf:type schema:PropertyValue
57 N4c53ddb1c42c41a2875fdd489ac6bf23 schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 N569e05a896cf438ea31195ca3b4a60d8 schema:issueNumber 3
60 rdf:type schema:PublicationIssue
61 N6e582a6620be410ea367cba20f4a0e07 rdf:first sg:person.011636042271.02
62 rdf:rest N9ae29dc99a2c4058bac2524296474027
63 N83e13e8eca9a4f2aa1468bb5f69536bf schema:volumeNumber 7
64 rdf:type schema:PublicationVolume
65 N8b566c779ca84f78afedc7cb8837a49e rdf:first sg:person.015253401573.30
66 rdf:rest N6e582a6620be410ea367cba20f4a0e07
67 N9ae29dc99a2c4058bac2524296474027 rdf:first sg:person.010320662413.19
68 rdf:rest rdf:nil
69 Na0b1879e929f486da0acd8176611686e schema:name doi
70 schema:value 10.1007/s000370050010
71 rdf:type schema:PropertyValue
72 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
73 schema:name Information and Computing Sciences
74 rdf:type schema:DefinedTerm
75 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
76 schema:name Artificial Intelligence and Image Processing
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
79 schema:name Computation Theory and Mathematics
80 rdf:type schema:DefinedTerm
81 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
82 schema:name Psychology and Cognitive Sciences
83 rdf:type schema:DefinedTerm
84 anzsrc-for:1702 schema:inDefinedTermSet anzsrc-for:
85 schema:name Cognitive Sciences
86 rdf:type schema:DefinedTerm
87 sg:journal.1136224 schema:issn 1016-3328
88 1420-8954
89 schema:name computational complexity
90 schema:publisher Springer Nature
91 rdf:type schema:Periodical
92 sg:person.010320662413.19 schema:affiliation grid-institutes:grid.16750.35
93 schema:familyName Yao
94 schema:givenName A.C.
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010320662413.19
96 rdf:type schema:Person
97 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
98 schema:familyName Karpinski
99 schema:givenName M.
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
101 rdf:type schema:Person
102 sg:person.015253401573.30 schema:affiliation grid-institutes:grid.29857.31
103 schema:familyName Grigoriev
104 schema:givenName D.
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015253401573.30
106 rdf:type schema:Person
107 grid-institutes:grid.10388.32 schema:alternateName Dept. of Computer Science, University of Bonn, D-53117 Bonn, e-mail: marek@cs.uni-bonn.de, DE
108 schema:name Dept. of Computer Science, University of Bonn, D-53117 Bonn, e-mail: marek@cs.uni-bonn.de, DE
109 rdf:type schema:Organization
110 grid-institutes:grid.16750.35 schema:alternateName Dept. of Computer Science, Princeton University, Princeton, New Jersey 08544, USA, e-mail: yao@cs.princeton.edu, US
111 schema:name Dept. of Computer Science, Princeton University, Princeton, New Jersey 08544, USA, e-mail: yao@cs.princeton.edu, US
112 rdf:type schema:Organization
113 grid-institutes:grid.29857.31 schema:alternateName Dept. of Computer Science and Mathematics, Penn State University, University Park, USA, e-mail: dima@cse.psu.edu, US
114 schema:name Dept. of Computer Science and Mathematics, Penn State University, University Park, USA, e-mail: dima@cse.psu.edu, US
115 rdf:type schema:Organization
 




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


...