Local Property Reconstruction and Monotonicity View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Michael Saks , C. Seshadhri

ABSTRACT

We propose a general model of local property reconstruction. Suppose we have a function f on domain Γ, which is supposed to have a particular property \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{P}$\end{document}, but may not have the property. We would like a procedure that produces a function g that has property \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{P}$\end{document} and is close to f (according to some suitable metric). The reconstruction procedure, called a filter, has the following form. The procedure takes as input an element x of Γ and outputs g(x). The procedure has oracle access to the function f and uses a single short random string ρ, but is otherwise deterministic.This model was inspired by a related model of online property reconstruction that was introduced by by Ailon, Chazelle, Comandur and Liu (2004). It is related to the property testing model, and extends the framework that is used in the model of locally decodable codes. A similar model, in the context of hypergraph properties, was independently proposed and studied by Austin and Tao (2008).We specifically consider the property of monotonicity and develop an efficient local filter for this property. The input f is a real valued function defined over the domain {1,...,n}d (where n is viewed as large and d as a constant). The function is monotone if the following property holds: for two domain elements x and y, if x ≤ y (in the product order) then f(x) ≤ f(y). Given x, our filter outputs the value g(x) in (logn)O(1) time and uses a random seed ρ of the same size. With high probability, the ratio of the Hamming distance between g and f to the minimum possible Hamming distance between a monotone function and f is bounded above by a function of d (independent of n). More... »

PAGES

346-354

Book

TITLE

Property Testing

ISBN

978-3-642-16366-1
978-3-642-16367-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-16367-8_29

DOI

http://dx.doi.org/10.1007/978-3-642-16367-8_29

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, Rutgers University, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Mathematics, Rutgers University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks", 
        "givenName": "Michael", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "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": "Seshadhri", 
        "givenName": "C.", 
        "id": "sg:person.07623230105.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07623230105.32"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "We propose a general model of local property reconstruction. Suppose we have a function f on domain \u0393, which is supposed to have a particular property \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal{P}$\\end{document}, but may not have the property. We would like a procedure that produces a function g that has property \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal{P}$\\end{document} and is close to f (according to some suitable metric). The reconstruction procedure, called a filter, has the following form. The procedure takes as input an element x of \u0393 and outputs g(x). The procedure has oracle access to the function f and uses a single short random string \u03c1, but is otherwise deterministic.This model was inspired by a related model of online property reconstruction that was introduced by by Ailon, Chazelle, Comandur and Liu (2004). It is related to the property testing model, and extends the framework that is used in the model of locally decodable codes. A similar model, in the context of hypergraph properties, was independently proposed and studied by Austin and Tao (2008).We specifically consider the property of monotonicity and develop an efficient local filter for this property. The input f is a real valued function defined over the domain {1,...,n}d (where n is viewed as large and d as a constant). The function is monotone if the following property holds: for two domain elements x and y, if x\u2009\u2264\u2009y (in the product order) then f(x)\u2009\u2264\u2009f(y). Given x, our filter outputs the value g(x) in (logn)O(1) time and uses a random seed \u03c1 of the same size. With high probability, the ratio of the Hamming distance between g and f to the minimum possible Hamming distance between a monotone function and f is bounded above by a function of d (independent of n).", 
    "editor": [
      {
        "familyName": "Goldreich", 
        "givenName": "Oded", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-16367-8_29", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-16366-1", 
        "978-3-642-16367-8"
      ], 
      "name": "Property Testing", 
      "type": "Book"
    }, 
    "keywords": [
      "Hamming distance", 
      "property testing model", 
      "decodable codes", 
      "property reconstruction", 
      "oracle access", 
      "property of monotonicity", 
      "hypergraph properties", 
      "related models", 
      "local filters", 
      "input f", 
      "testing models", 
      "general model", 
      "Chazelle", 
      "model", 
      "reconstruction", 
      "reconstruction procedure", 
      "filter", 
      "code", 
      "high probability", 
      "particular properties", 
      "framework", 
      "similar models", 
      "access", 
      "input", 
      "Ailon", 
      "domain", 
      "function f", 
      "monotonicity", 
      "same size", 
      "distance", 
      "output", 
      "context", 
      "monotone functions", 
      "function", 
      "probability", 
      "procedure", 
      "time", 
      "Liu", 
      "Tao", 
      "Austin", 
      "form", 
      "size", 
      "properties", 
      "element x", 
      "values", 
      "ratio"
    ], 
    "name": "Local Property Reconstruction and Monotonicity", 
    "pagination": "346-354", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044910402"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-16367-8_29"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-16367-8_29", 
      "https://app.dimensions.ai/details/publication/pub.1044910402"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-09-02T16:17", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/chapter/chapter_48.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-16367-8_29"
  }
]
 

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-16367-8_29'

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-16367-8_29'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-16367-8_29'

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-16367-8_29'


 

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

115 TRIPLES      22 PREDICATES      71 URIs      64 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-16367-8_29 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author Nd407120f9f324faab67f42053df8a0a3
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description We propose a general model of local property reconstruction. Suppose we have a function f on domain Γ, which is supposed to have a particular property \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{P}$\end{document}, but may not have the property. We would like a procedure that produces a function g that has property \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal{P}$\end{document} and is close to f (according to some suitable metric). The reconstruction procedure, called a filter, has the following form. The procedure takes as input an element x of Γ and outputs g(x). The procedure has oracle access to the function f and uses a single short random string ρ, but is otherwise deterministic.This model was inspired by a related model of online property reconstruction that was introduced by by Ailon, Chazelle, Comandur and Liu (2004). It is related to the property testing model, and extends the framework that is used in the model of locally decodable codes. A similar model, in the context of hypergraph properties, was independently proposed and studied by Austin and Tao (2008).We specifically consider the property of monotonicity and develop an efficient local filter for this property. The input f is a real valued function defined over the domain {1,...,n}d (where n is viewed as large and d as a constant). The function is monotone if the following property holds: for two domain elements x and y, if x ≤ y (in the product order) then f(x) ≤ f(y). Given x, our filter outputs the value g(x) in (logn)O(1) time and uses a random seed ρ of the same size. With high probability, the ratio of the Hamming distance between g and f to the minimum possible Hamming distance between a monotone function and f is bounded above by a function of d (independent of n).
7 schema:editor N5395e68ef27e422f91b723c36c512346
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N89bd135fb2c4460697d869c6ff28f14e
11 schema:keywords Ailon
12 Austin
13 Chazelle
14 Hamming distance
15 Liu
16 Tao
17 access
18 code
19 context
20 decodable codes
21 distance
22 domain
23 element x
24 filter
25 form
26 framework
27 function
28 function f
29 general model
30 high probability
31 hypergraph properties
32 input
33 input f
34 local filters
35 model
36 monotone functions
37 monotonicity
38 oracle access
39 output
40 particular properties
41 probability
42 procedure
43 properties
44 property of monotonicity
45 property reconstruction
46 property testing model
47 ratio
48 reconstruction
49 reconstruction procedure
50 related models
51 same size
52 similar models
53 size
54 testing models
55 time
56 values
57 schema:name Local Property Reconstruction and Monotonicity
58 schema:pagination 346-354
59 schema:productId N93a7e815ecec4f9e8d8403542583f78b
60 Nc9b5fdc1cfd74b78ad8ec3830847e51b
61 schema:publisher Ne1d3454be4ee4f45a7d317ec77f1b87e
62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044910402
63 https://doi.org/10.1007/978-3-642-16367-8_29
64 schema:sdDatePublished 2022-09-02T16:17
65 schema:sdLicense https://scigraph.springernature.com/explorer/license/
66 schema:sdPublisher Nf9e79f428f664564a530f6ecca3c1f42
67 schema:url https://doi.org/10.1007/978-3-642-16367-8_29
68 sgo:license sg:explorer/license/
69 sgo:sdDataset chapters
70 rdf:type schema:Chapter
71 N0c247c65fec640a1bae19f1da7ff30ef schema:familyName Goldreich
72 schema:givenName Oded
73 rdf:type schema:Person
74 N5395e68ef27e422f91b723c36c512346 rdf:first N0c247c65fec640a1bae19f1da7ff30ef
75 rdf:rest rdf:nil
76 N89bd135fb2c4460697d869c6ff28f14e schema:isbn 978-3-642-16366-1
77 978-3-642-16367-8
78 schema:name Property Testing
79 rdf:type schema:Book
80 N93a7e815ecec4f9e8d8403542583f78b schema:name dimensions_id
81 schema:value pub.1044910402
82 rdf:type schema:PropertyValue
83 Nc3d7a41e7e4142778ed1711ff288fcc9 rdf:first sg:person.07623230105.32
84 rdf:rest rdf:nil
85 Nc9b5fdc1cfd74b78ad8ec3830847e51b schema:name doi
86 schema:value 10.1007/978-3-642-16367-8_29
87 rdf:type schema:PropertyValue
88 Nd407120f9f324faab67f42053df8a0a3 rdf:first sg:person.011520224512.05
89 rdf:rest Nc3d7a41e7e4142778ed1711ff288fcc9
90 Ne1d3454be4ee4f45a7d317ec77f1b87e schema:name Springer Nature
91 rdf:type schema:Organisation
92 Nf9e79f428f664564a530f6ecca3c1f42 schema:name Springer Nature - SN SciGraph project
93 rdf:type schema:Organization
94 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
95 schema:name Mathematical Sciences
96 rdf:type schema:DefinedTerm
97 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
98 schema:name Statistics
99 rdf:type schema:DefinedTerm
100 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
101 schema:familyName Saks
102 schema:givenName Michael
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
104 rdf:type schema:Person
105 sg:person.07623230105.32 schema:affiliation grid-institutes:grid.481551.c
106 schema:familyName Seshadhri
107 schema:givenName C.
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07623230105.32
109 rdf:type schema:Person
110 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University, USA
111 schema:name Department of Mathematics, Rutgers University, USA
112 rdf:type schema:Organization
113 grid-institutes:grid.481551.c schema:alternateName IBM Almaden Research Center, USA
114 schema:name IBM Almaden Research Center, USA
115 rdf:type schema:Organization
 




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


...