Testing Linear-Invariant Non-linear Properties: A Short Report View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Arnab Bhattacharyya , Victor Chen , Madhu Sudan , Ning Xie

ABSTRACT

The rich collection of successes in property testing raises a natural question: Why are so many different properties turning out to be locally testable? Are there some broad “features” of properties that make them testable? Kaufman and Sudan (STOC 2008) proposed the study of the relationship between the invariances satisfied by a property and its testability. Particularly, they studied properties that were invariant under linear transformations of the domain and gave a characterization of testability in certain settings. However, the properties that they examined were also linear. This led us to investigate linear-invariant properties that are not necessarily linear. Here we describe some of the resulting works which consider natural linear-invariant properties, specifically properties that are described by forbidden patterns of values that a function can take, and show testability under various settings. More... »

PAGES

260-268

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/11", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Medical and Health Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Clinical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "MIT CSAIL, Cambridge, MA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT CSAIL, Cambridge, MA"
          ], 
          "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": "Institute of Theoretical Computer Science, Tsinghua University, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "Institute of Theoretical Computer Science, Tsinghua University, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Victor", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Microsoft Research New England, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Microsoft Research New England, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sudan", 
        "givenName": "Madhu", 
        "id": "sg:person.014663420265.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT CSAIL, Cambridge, MA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT CSAIL, Cambridge, MA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Xie", 
        "givenName": "Ning", 
        "id": "sg:person.011416655253.73", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011416655253.73"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "The rich collection of successes in property testing raises a natural question: Why are so many different properties turning out to be locally testable? Are there some broad \u201cfeatures\u201d of properties that make them testable? Kaufman and Sudan (STOC 2008) proposed the study of the relationship between the invariances satisfied by a property and its testability. Particularly, they studied properties that were invariant under linear transformations of the domain and gave a characterization of testability in certain settings. However, the properties that they examined were also linear. This led us to investigate linear-invariant properties that are not necessarily linear. Here we describe some of the resulting works which consider natural linear-invariant properties, specifically properties that are described by forbidden patterns of values that a function can take, and show testability under various settings.", 
    "editor": [
      {
        "familyName": "Goldreich", 
        "givenName": "Oded", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-16367-8_18", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-16366-1", 
        "978-3-642-16367-8"
      ], 
      "name": "Property Testing", 
      "type": "Book"
    }, 
    "keywords": [
      "different properties", 
      "properties", 
      "certain settings", 
      "short report", 
      "property testing", 
      "characterization", 
      "setting", 
      "report", 
      "testing", 
      "study", 
      "transformation", 
      "Sudan", 
      "work", 
      "patterns", 
      "function", 
      "relationship", 
      "success", 
      "features", 
      "values", 
      "collection", 
      "questions", 
      "domain", 
      "rich collection", 
      "Kaufman", 
      "forbidden patterns", 
      "linear transformation", 
      "natural question", 
      "invariance", 
      "testability", 
      "characterization of testability", 
      "linear-invariant properties", 
      "natural linear-invariant properties"
    ], 
    "name": "Testing Linear-Invariant Non-linear Properties: A Short Report", 
    "pagination": "260-268", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1000813701"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-16367-8_18"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-16367-8_18", 
      "https://app.dimensions.ai/details/publication/pub.1000813701"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:07", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_117.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-16367-8_18"
  }
]
 

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_18'

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_18'

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_18'

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_18'


 

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

118 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-16367-8_18 schema:about anzsrc-for:11
2 anzsrc-for:1103
3 schema:author Nbf4899bf31b942a1ba5c24c7685dbfb9
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description The rich collection of successes in property testing raises a natural question: Why are so many different properties turning out to be locally testable? Are there some broad “features” of properties that make them testable? Kaufman and Sudan (STOC 2008) proposed the study of the relationship between the invariances satisfied by a property and its testability. Particularly, they studied properties that were invariant under linear transformations of the domain and gave a characterization of testability in certain settings. However, the properties that they examined were also linear. This led us to investigate linear-invariant properties that are not necessarily linear. Here we describe some of the resulting works which consider natural linear-invariant properties, specifically properties that are described by forbidden patterns of values that a function can take, and show testability under various settings.
7 schema:editor Na79996936a0840e9a6b325841237753d
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nf0ab7006fb1e478182cdd61f591d08c5
12 schema:keywords Kaufman
13 Sudan
14 certain settings
15 characterization
16 characterization of testability
17 collection
18 different properties
19 domain
20 features
21 forbidden patterns
22 function
23 invariance
24 linear transformation
25 linear-invariant properties
26 natural linear-invariant properties
27 natural question
28 patterns
29 properties
30 property testing
31 questions
32 relationship
33 report
34 rich collection
35 setting
36 short report
37 study
38 success
39 testability
40 testing
41 transformation
42 values
43 work
44 schema:name Testing Linear-Invariant Non-linear Properties: A Short Report
45 schema:pagination 260-268
46 schema:productId Nb912891a89a6451d8a5c314b7c0019d2
47 Nb9a85d4886374d239e35b04f05714760
48 schema:publisher Nde928ad2751342e99dec8c03ddc09b78
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000813701
50 https://doi.org/10.1007/978-3-642-16367-8_18
51 schema:sdDatePublished 2022-01-01T19:07
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher Nc5800896a7f04368897baf27ee00d1e2
54 schema:url https://doi.org/10.1007/978-3-642-16367-8_18
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N0e4cee5a314f40a0a7beec3ad7b2e4f2 schema:familyName Goldreich
59 schema:givenName Oded
60 rdf:type schema:Person
61 N9e6a98b4b5ff4818b3bf3bd17639f632 rdf:first Nf792b09171674157a3c333d4ef30acde
62 rdf:rest Ne1a902347d934a6fb2bf6cb5aa200934
63 Na79996936a0840e9a6b325841237753d rdf:first N0e4cee5a314f40a0a7beec3ad7b2e4f2
64 rdf:rest rdf:nil
65 Nb912891a89a6451d8a5c314b7c0019d2 schema:name dimensions_id
66 schema:value pub.1000813701
67 rdf:type schema:PropertyValue
68 Nb9a85d4886374d239e35b04f05714760 schema:name doi
69 schema:value 10.1007/978-3-642-16367-8_18
70 rdf:type schema:PropertyValue
71 Nbf4899bf31b942a1ba5c24c7685dbfb9 rdf:first sg:person.012357145015.18
72 rdf:rest N9e6a98b4b5ff4818b3bf3bd17639f632
73 Nc5800896a7f04368897baf27ee00d1e2 schema:name Springer Nature - SN SciGraph project
74 rdf:type schema:Organization
75 Nde928ad2751342e99dec8c03ddc09b78 schema:name Springer Nature
76 rdf:type schema:Organisation
77 Ne1a902347d934a6fb2bf6cb5aa200934 rdf:first sg:person.014663420265.17
78 rdf:rest Need46420f2f14ad2868cd5fccbe684d0
79 Need46420f2f14ad2868cd5fccbe684d0 rdf:first sg:person.011416655253.73
80 rdf:rest rdf:nil
81 Nf0ab7006fb1e478182cdd61f591d08c5 schema:isbn 978-3-642-16366-1
82 978-3-642-16367-8
83 schema:name Property Testing
84 rdf:type schema:Book
85 Nf792b09171674157a3c333d4ef30acde schema:affiliation grid-institutes:grid.12527.33
86 schema:familyName Chen
87 schema:givenName Victor
88 rdf:type schema:Person
89 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
90 schema:name Medical and Health Sciences
91 rdf:type schema:DefinedTerm
92 anzsrc-for:1103 schema:inDefinedTermSet anzsrc-for:
93 schema:name Clinical Sciences
94 rdf:type schema:DefinedTerm
95 sg:person.011416655253.73 schema:affiliation grid-institutes:grid.116068.8
96 schema:familyName Xie
97 schema:givenName Ning
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011416655253.73
99 rdf:type schema:Person
100 sg:person.012357145015.18 schema:affiliation grid-institutes:grid.116068.8
101 schema:familyName Bhattacharyya
102 schema:givenName Arnab
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357145015.18
104 rdf:type schema:Person
105 sg:person.014663420265.17 schema:affiliation grid-institutes:None
106 schema:familyName Sudan
107 schema:givenName Madhu
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
109 rdf:type schema:Person
110 grid-institutes:None schema:alternateName Microsoft Research New England, Cambridge, MA, USA
111 schema:name Microsoft Research New England, Cambridge, MA, USA
112 rdf:type schema:Organization
113 grid-institutes:grid.116068.8 schema:alternateName MIT CSAIL, Cambridge, MA
114 schema:name MIT CSAIL, Cambridge, MA
115 rdf:type schema:Organization
116 grid-institutes:grid.12527.33 schema:alternateName Institute of Theoretical Computer Science, Tsinghua University, Beijing, China
117 schema:name Institute of Theoretical Computer Science, Tsinghua University, Beijing, China
118 rdf:type schema:Organization
 




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


...