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/grid.419815.0", 
          "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", 
      "characterization", 
      "property testing", 
      "transformation", 
      "linear-invariant properties", 
      "work", 
      "certain settings", 
      "values", 
      "short report", 
      "rich collection", 
      "natural question", 
      "features", 
      "study", 
      "linear transformation", 
      "setting", 
      "forbidden patterns", 
      "report", 
      "testing", 
      "relationship", 
      "domain", 
      "patterns", 
      "function", 
      "collection", 
      "success", 
      "Sudan", 
      "invariance", 
      "questions", 
      "Kaufman", 
      "testability"
    ], 
    "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-05-20T07:46", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_352.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.

116 TRIPLES      23 PREDICATES      56 URIs      49 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 Nf3aa02902c1a46c9b5167332c432b5ec
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 N4581818f6a1340a6aeb2b4fe049788cc
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N923fabb59abe412d9d1a24716122606d
12 schema:keywords Kaufman
13 Sudan
14 certain settings
15 characterization
16 collection
17 different properties
18 domain
19 features
20 forbidden patterns
21 function
22 invariance
23 linear transformation
24 linear-invariant properties
25 natural question
26 patterns
27 properties
28 property testing
29 questions
30 relationship
31 report
32 rich collection
33 setting
34 short report
35 study
36 success
37 testability
38 testing
39 transformation
40 values
41 work
42 schema:name Testing Linear-Invariant Non-linear Properties: A Short Report
43 schema:pagination 260-268
44 schema:productId N1f2b92ced7914a73ac3e104332653ae9
45 N48bedc58538245cbbda92302a6631de8
46 schema:publisher N3def988fde5848079367025a943155f0
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000813701
48 https://doi.org/10.1007/978-3-642-16367-8_18
49 schema:sdDatePublished 2022-05-20T07:46
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher Nf6e02889684547b1b622e4490d26f686
52 schema:url https://doi.org/10.1007/978-3-642-16367-8_18
53 sgo:license sg:explorer/license/
54 sgo:sdDataset chapters
55 rdf:type schema:Chapter
56 N17d75b3adc1e4f6c8a44c98fc1c15df5 schema:familyName Goldreich
57 schema:givenName Oded
58 rdf:type schema:Person
59 N1f2b92ced7914a73ac3e104332653ae9 schema:name dimensions_id
60 schema:value pub.1000813701
61 rdf:type schema:PropertyValue
62 N3def988fde5848079367025a943155f0 schema:name Springer Nature
63 rdf:type schema:Organisation
64 N4581818f6a1340a6aeb2b4fe049788cc rdf:first N17d75b3adc1e4f6c8a44c98fc1c15df5
65 rdf:rest rdf:nil
66 N48bedc58538245cbbda92302a6631de8 schema:name doi
67 schema:value 10.1007/978-3-642-16367-8_18
68 rdf:type schema:PropertyValue
69 N4c39a625ebc6456ebe27d280e2d95fed rdf:first sg:person.011416655253.73
70 rdf:rest rdf:nil
71 N7a82aed83e34435f8918335a7f0abee2 rdf:first Nfc0fc42e935e4acb953c4762bad08dae
72 rdf:rest Nddfaa8c7aec44066996e3da91e7c2bae
73 N923fabb59abe412d9d1a24716122606d schema:isbn 978-3-642-16366-1
74 978-3-642-16367-8
75 schema:name Property Testing
76 rdf:type schema:Book
77 Nddfaa8c7aec44066996e3da91e7c2bae rdf:first sg:person.014663420265.17
78 rdf:rest N4c39a625ebc6456ebe27d280e2d95fed
79 Nf3aa02902c1a46c9b5167332c432b5ec rdf:first sg:person.012357145015.18
80 rdf:rest N7a82aed83e34435f8918335a7f0abee2
81 Nf6e02889684547b1b622e4490d26f686 schema:name Springer Nature - SN SciGraph project
82 rdf:type schema:Organization
83 Nfc0fc42e935e4acb953c4762bad08dae schema:affiliation grid-institutes:grid.12527.33
84 schema:familyName Chen
85 schema:givenName Victor
86 rdf:type schema:Person
87 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
88 schema:name Medical and Health Sciences
89 rdf:type schema:DefinedTerm
90 anzsrc-for:1103 schema:inDefinedTermSet anzsrc-for:
91 schema:name Clinical Sciences
92 rdf:type schema:DefinedTerm
93 sg:person.011416655253.73 schema:affiliation grid-institutes:grid.116068.8
94 schema:familyName Xie
95 schema:givenName Ning
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011416655253.73
97 rdf:type schema:Person
98 sg:person.012357145015.18 schema:affiliation grid-institutes:grid.116068.8
99 schema:familyName Bhattacharyya
100 schema:givenName Arnab
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357145015.18
102 rdf:type schema:Person
103 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.419815.0
104 schema:familyName Sudan
105 schema:givenName Madhu
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
107 rdf:type schema:Person
108 grid-institutes:grid.116068.8 schema:alternateName MIT CSAIL, Cambridge, MA
109 schema:name MIT CSAIL, Cambridge, MA
110 rdf:type schema:Organization
111 grid-institutes:grid.12527.33 schema:alternateName Institute of Theoretical Computer Science, Tsinghua University, Beijing, China
112 schema:name Institute of Theoretical Computer Science, Tsinghua University, Beijing, China
113 rdf:type schema:Organization
114 grid-institutes:grid.419815.0 schema:alternateName Microsoft Research New England, Cambridge, MA, USA
115 schema:name Microsoft Research New England, Cambridge, MA, USA
116 rdf:type schema:Organization
 




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


...