Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Arnab Bhattacharyya , Elena Grigorescu , Madhav Jha , Kyomin Jung , Sofya Raskhodnikova , David P. Woodruff

ABSTRACT

Given a directed graph G = (V,E) and an integer k ≥ 1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, EH) that has (1) the same transitive-closure as G and (2) diameter at most k. Transitive-closure spanners are a common abstraction for applications in access control, property testing and data structures.We show a connection between 2-TC-spanners and local monotonicity reconstructors. A local monotonicity reconstructor, introduced by Saks and Seshadhri (SIAM Journal on Computing, 2010), is a randomized algorithm that, given access to an oracle for an almost monotone function f : [m]d →ℝ, can quickly evaluate a related function g : [m]d →ℝ which is guaranteed to be monotone. Furthermore, the reconstructor can be implemented in a distributed manner. We show that an efficient local monotonicity reconstructor implies a sparse 2-TC-spanner of the directed hypergrid (hypercube), providing a new technique for proving lower bounds for local monotonicity reconstructors. Our connection is, in fact, more general: an efficient local monotonicity reconstructor for functions on any partially ordered set (poset) implies a sparse 2-TC-spanner of the directed acyclic graph corresponding to the poset.We present tight upper and lower bounds on the size of the sparsest 2-TC-spanners of the directed hypercube and hypergrid. These bounds imply tighter lower bounds for local monotonicity reconstructors that nearly match the known upper bounds. More... »

PAGES

448-461

Book

TITLE

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-642-15368-6
978-3-642-15369-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-15369-3_34

DOI

http://dx.doi.org/10.1007/978-3-642-15369-3_34

DIMENSIONS

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


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/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Massachusetts Institute of Technology, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Massachusetts Institute of Technology, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bhattacharyya", 
        "givenName": "Arnab", 
        "id": "sg:person.012357145015.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357145015.18"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Massachusetts Institute of Technology, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Massachusetts Institute of Technology, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Grigorescu", 
        "givenName": "Elena", 
        "id": "sg:person.014612515147.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014612515147.15"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Pennsylvania State University, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Pennsylvania State University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jha", 
        "givenName": "Madhav", 
        "id": "sg:person.010762463660.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010762463660.35"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Korea Advanced Institute of Science and Technology, Korea", 
          "id": "http://www.grid.ac/institutes/grid.37172.30", 
          "name": [
            "Korea Advanced Institute of Science and Technology, Korea"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jung", 
        "givenName": "Kyomin", 
        "id": "sg:person.011140666573.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011140666573.35"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Pennsylvania State University, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Pennsylvania State University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Raskhodnikova", 
        "givenName": "Sofya", 
        "id": "sg:person.07502404747.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07502404747.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Almaden Research Center, USA", 
          "id": "http://www.grid.ac/institutes/grid.481551.c", 
          "name": [
            "IBM Almaden Research Center, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Woodruff", 
        "givenName": "David P.", 
        "id": "sg:person.012727410605.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "Given a directed graph G\u2009=\u2009(V,E) and an integer k\u2009\u2265\u20091, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H\u2009=\u2009(V, EH) that has (1)\u00a0the same transitive-closure as G and (2) diameter at most\u00a0k. Transitive-closure spanners are a common abstraction for applications in access control, property testing and data structures.We show a connection between 2-TC-spanners and local monotonicity reconstructors. A local monotonicity reconstructor, introduced by Saks and Seshadhri (SIAM Journal on Computing, 2010), is a randomized algorithm that, given access to an oracle for an almost monotone function f : [m]d \u2192\u211d, can quickly evaluate a related function g : [m]d \u2192\u211d which is guaranteed to be monotone. Furthermore, the reconstructor can be implemented in a distributed manner. We show that an efficient local monotonicity reconstructor implies a sparse 2-TC-spanner of the directed hypergrid (hypercube), providing a new technique for proving lower bounds for local monotonicity reconstructors. Our connection is, in fact, more general: an efficient local monotonicity reconstructor for functions on any partially ordered set (poset) implies a sparse 2-TC-spanner of the directed acyclic graph corresponding to the poset.We present tight upper and lower bounds on the size of the sparsest 2-TC-spanners of the directed hypercube and hypergrid. These bounds imply tighter lower bounds for local monotonicity reconstructors that nearly match the known upper bounds.", 
    "editor": [
      {
        "familyName": "Serna", 
        "givenName": "Maria", 
        "type": "Person"
      }, 
      {
        "familyName": "Shaltiel", 
        "givenName": "Ronen", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-15369-3_34", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-15368-6", 
        "978-3-642-15369-3"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "lower bounds", 
      "known upper bounds", 
      "tight lower bounds", 
      "upper bounds", 
      "graph H", 
      "randomized algorithm", 
      "bounds", 
      "graph G", 
      "monotone function f", 
      "reconstructor", 
      "function f", 
      "acyclic graph", 
      "data structure", 
      "hypergrid", 
      "spanners", 
      "posets", 
      "graph", 
      "hypercube", 
      "related functions", 
      "property testing", 
      "algorithm", 
      "new technique", 
      "function", 
      "connection", 
      "set", 
      "oracle", 
      "common abstraction", 
      "applications", 
      "Sak", 
      "Seshadhri", 
      "structure", 
      "technique", 
      "control", 
      "fact", 
      "access control", 
      "size", 
      "reconstruction", 
      "abstraction", 
      "manner", 
      "diameter", 
      "testing", 
      "access"
    ], 
    "name": "Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners", 
    "pagination": "448-461", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1035546834"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-15369-3_34"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-15369-3_34", 
      "https://app.dimensions.ai/details/publication/pub.1035546834"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:51", 
    "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/chapter/chapter_331.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-15369-3_34"
  }
]
 

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/978-3-642-15369-3_34'

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/978-3-642-15369-3_34'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-15369-3_34'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-15369-3_34'


 

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

160 TRIPLES      22 PREDICATES      67 URIs      60 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-15369-3_34 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N6a3ed49a63c5454f801a4b67ec04ecc5
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description Given a directed graph G = (V,E) and an integer k ≥ 1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, EH) that has (1) the same transitive-closure as G and (2) diameter at most k. Transitive-closure spanners are a common abstraction for applications in access control, property testing and data structures.We show a connection between 2-TC-spanners and local monotonicity reconstructors. A local monotonicity reconstructor, introduced by Saks and Seshadhri (SIAM Journal on Computing, 2010), is a randomized algorithm that, given access to an oracle for an almost monotone function f : [m]d →ℝ, can quickly evaluate a related function g : [m]d →ℝ which is guaranteed to be monotone. Furthermore, the reconstructor can be implemented in a distributed manner. We show that an efficient local monotonicity reconstructor implies a sparse 2-TC-spanner of the directed hypergrid (hypercube), providing a new technique for proving lower bounds for local monotonicity reconstructors. Our connection is, in fact, more general: an efficient local monotonicity reconstructor for functions on any partially ordered set (poset) implies a sparse 2-TC-spanner of the directed acyclic graph corresponding to the poset.We present tight upper and lower bounds on the size of the sparsest 2-TC-spanners of the directed hypercube and hypergrid. These bounds imply tighter lower bounds for local monotonicity reconstructors that nearly match the known upper bounds.
7 schema:editor Ncf35067a32bd46efa1114a6502405c6b
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N3cff339b7fe4415680accbed961c4004
11 schema:keywords Sak
12 Seshadhri
13 abstraction
14 access
15 access control
16 acyclic graph
17 algorithm
18 applications
19 bounds
20 common abstraction
21 connection
22 control
23 data structure
24 diameter
25 fact
26 function
27 function f
28 graph
29 graph G
30 graph H
31 hypercube
32 hypergrid
33 known upper bounds
34 lower bounds
35 manner
36 monotone function f
37 new technique
38 oracle
39 posets
40 property testing
41 randomized algorithm
42 reconstruction
43 reconstructor
44 related functions
45 set
46 size
47 spanners
48 structure
49 technique
50 testing
51 tight lower bounds
52 upper bounds
53 schema:name Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners
54 schema:pagination 448-461
55 schema:productId Nbd9766feab1943c6ae129ade781c7fd1
56 Ndabb13a8e83645e58a8d954e55b98e32
57 schema:publisher Nfc7fb8710cea4831a7c1796d3124c765
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035546834
59 https://doi.org/10.1007/978-3-642-15369-3_34
60 schema:sdDatePublished 2022-12-01T06:51
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher N3b43281a3c0649c5bdf7ffef053e98ef
63 schema:url https://doi.org/10.1007/978-3-642-15369-3_34
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N0a522cd40fe241cba6f4ba30a0d53617 schema:familyName Shaltiel
68 schema:givenName Ronen
69 rdf:type schema:Person
70 N13018c1e93994fa9a8e7e5fb63e5bdff rdf:first sg:person.010762463660.35
71 rdf:rest N3e7c942aecbb4c01a4fe292393741e15
72 N3b43281a3c0649c5bdf7ffef053e98ef schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
74 N3cff339b7fe4415680accbed961c4004 schema:isbn 978-3-642-15368-6
75 978-3-642-15369-3
76 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
77 rdf:type schema:Book
78 N3e7c942aecbb4c01a4fe292393741e15 rdf:first sg:person.011140666573.35
79 rdf:rest Nf84478cd25fe4ef68fad5058e4d88e22
80 N4c88f329504945ab805c80018990722b rdf:first sg:person.014612515147.15
81 rdf:rest N13018c1e93994fa9a8e7e5fb63e5bdff
82 N4f6e458c1bd24a118be4151caff4a298 schema:familyName Serna
83 schema:givenName Maria
84 rdf:type schema:Person
85 N6a3ed49a63c5454f801a4b67ec04ecc5 rdf:first sg:person.012357145015.18
86 rdf:rest N4c88f329504945ab805c80018990722b
87 N799a2eb19a4647ecbfb553e00d0c4907 schema:familyName Rolim
88 schema:givenName José
89 rdf:type schema:Person
90 N8f3f0199f4eb4c0186a733f6b37b5fa9 rdf:first N799a2eb19a4647ecbfb553e00d0c4907
91 rdf:rest rdf:nil
92 Nafb9cea8ff234a44b4aab330d6e81fa0 rdf:first sg:person.012727410605.86
93 rdf:rest rdf:nil
94 Nbd9766feab1943c6ae129ade781c7fd1 schema:name dimensions_id
95 schema:value pub.1035546834
96 rdf:type schema:PropertyValue
97 Nbfe8fc01b011484cb13a34c34f5238a6 schema:familyName Jansen
98 schema:givenName Klaus
99 rdf:type schema:Person
100 Nc2059d31b2e44740990bee9f301feb74 rdf:first Nbfe8fc01b011484cb13a34c34f5238a6
101 rdf:rest N8f3f0199f4eb4c0186a733f6b37b5fa9
102 Ncf35067a32bd46efa1114a6502405c6b rdf:first N4f6e458c1bd24a118be4151caff4a298
103 rdf:rest Ne7aadb51f84a41f09f31074487849012
104 Ndabb13a8e83645e58a8d954e55b98e32 schema:name doi
105 schema:value 10.1007/978-3-642-15369-3_34
106 rdf:type schema:PropertyValue
107 Ne7aadb51f84a41f09f31074487849012 rdf:first N0a522cd40fe241cba6f4ba30a0d53617
108 rdf:rest Nc2059d31b2e44740990bee9f301feb74
109 Nf84478cd25fe4ef68fad5058e4d88e22 rdf:first sg:person.07502404747.45
110 rdf:rest Nafb9cea8ff234a44b4aab330d6e81fa0
111 Nfc7fb8710cea4831a7c1796d3124c765 schema:name Springer Nature
112 rdf:type schema:Organisation
113 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
114 schema:name Information and Computing Sciences
115 rdf:type schema:DefinedTerm
116 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
117 schema:name Information Systems
118 rdf:type schema:DefinedTerm
119 sg:person.010762463660.35 schema:affiliation grid-institutes:grid.29857.31
120 schema:familyName Jha
121 schema:givenName Madhav
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010762463660.35
123 rdf:type schema:Person
124 sg:person.011140666573.35 schema:affiliation grid-institutes:grid.37172.30
125 schema:familyName Jung
126 schema:givenName Kyomin
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011140666573.35
128 rdf:type schema:Person
129 sg:person.012357145015.18 schema:affiliation grid-institutes:grid.116068.8
130 schema:familyName Bhattacharyya
131 schema:givenName Arnab
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357145015.18
133 rdf:type schema:Person
134 sg:person.012727410605.86 schema:affiliation grid-institutes:grid.481551.c
135 schema:familyName Woodruff
136 schema:givenName David P.
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86
138 rdf:type schema:Person
139 sg:person.014612515147.15 schema:affiliation grid-institutes:grid.116068.8
140 schema:familyName Grigorescu
141 schema:givenName Elena
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014612515147.15
143 rdf:type schema:Person
144 sg:person.07502404747.45 schema:affiliation grid-institutes:grid.29857.31
145 schema:familyName Raskhodnikova
146 schema:givenName Sofya
147 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07502404747.45
148 rdf:type schema:Person
149 grid-institutes:grid.116068.8 schema:alternateName Massachusetts Institute of Technology, USA
150 schema:name Massachusetts Institute of Technology, USA
151 rdf:type schema:Organization
152 grid-institutes:grid.29857.31 schema:alternateName Pennsylvania State University, USA
153 schema:name Pennsylvania State University, USA
154 rdf:type schema:Organization
155 grid-institutes:grid.37172.30 schema:alternateName Korea Advanced Institute of Science and Technology, Korea
156 schema:name Korea Advanced Institute of Science and Technology, Korea
157 rdf:type schema:Organization
158 grid-institutes:grid.481551.c schema:alternateName IBM Almaden Research Center, USA
159 schema:name IBM Almaden Research Center, USA
160 rdf:type schema:Organization
 




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


...