Invariance in Property Testing View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Madhu Sudan

ABSTRACT

Property testing considers the task of testing rapidly (in particular, with very few samples into the data), if some massive data satisfies some given property, or is far from satisfying the property. For “global properties”, i.e., properties that really depend somewhat on every piece of the data, one could ask how it can be tested by so few samples? We suggest that for “natural” properties, this should happen because the property is invariant under “nice” set of “relabellings” of the data. We refer to this set of relabellings as the “invariance class” of the property and advocate explicit identification of the invariance class of locally testable properties. Our hope is the explicit knowledge of the invariance class may lead to more general, broader, results.After pointing out the invariance classes associated with some the basic classes of testable properties, we focus on “algebraic properties” which seem to be characterized by the fact that the properties are themselves vector spaces, while their domains are also vector spaces and the properties are invariant under affine transformations of the domain. We survey recent results (obtained with Tali Kaufman, Elena Grigorescu and Eli Ben-Sasson) that give broad conditions that are sufficient for local testability among this class of properties, and some structural theorems that attempt to describe which properties exhibit the sufficient conditions. More... »

PAGES

211-227

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_12

DOI

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

DIMENSIONS

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


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/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Microsoft Research New England, One Memorial Drive, 02142, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.419815.0", 
          "name": [
            "Microsoft Research New England, One Memorial Drive, 02142, 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"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "Property testing considers the task of testing rapidly (in particular, with very few samples into the data), if some massive data satisfies some given property, or is far from satisfying the property. For \u201cglobal properties\u201d, i.e., properties that really depend somewhat on every piece of the data, one could ask how it can be tested by so few samples? We suggest that for \u201cnatural\u201d properties, this should happen because the property is invariant under \u201cnice\u201d set of \u201crelabellings\u201d of the data. We refer to this set of relabellings as the \u201cinvariance class\u201d of the property and advocate explicit identification of the invariance class of locally testable properties. Our hope is the explicit knowledge of the invariance class may lead to more general, broader, results.After pointing out the invariance classes associated with some the basic classes of testable properties, we focus on \u201calgebraic properties\u201d which seem to be characterized by the fact that the properties are themselves vector spaces, while their domains are also vector spaces and the properties are invariant under affine transformations of the domain. We survey recent results (obtained with Tali Kaufman, Elena Grigorescu and Eli Ben-Sasson) that give broad conditions that are sufficient for local testability among this class of properties, and some structural theorems that attempt to describe which properties exhibit the sufficient conditions.", 
    "editor": [
      {
        "familyName": "Goldreich", 
        "givenName": "Oded", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-16367-8_12", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-16366-1", 
        "978-3-642-16367-8"
      ], 
      "name": "Property Testing", 
      "type": "Book"
    }, 
    "keywords": [
      "vector space", 
      "testable properties", 
      "algebraic properties", 
      "sufficient conditions", 
      "structural theorem", 
      "global properties", 
      "data satisfies", 
      "basic classes", 
      "broad conditions", 
      "recent results", 
      "affine transformation", 
      "explicit identification", 
      "class", 
      "property testing", 
      "class of properties", 
      "space", 
      "theorem", 
      "invariance classes", 
      "properties", 
      "invariance", 
      "satisfies", 
      "local testability", 
      "relabelling", 
      "explicit knowledge", 
      "task of testing", 
      "set", 
      "domain", 
      "conditions", 
      "results", 
      "transformation", 
      "data", 
      "fact", 
      "task", 
      "testability", 
      "identification", 
      "pieces", 
      "testing", 
      "knowledge", 
      "samples", 
      "hope"
    ], 
    "name": "Invariance in Property Testing", 
    "pagination": "211-227", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1047100906"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-16367-8_12"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-16367-8_12", 
      "https://app.dimensions.ai/details/publication/pub.1047100906"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_49.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-16367-8_12"
  }
]
 

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

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

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

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


 

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

100 TRIPLES      23 PREDICATES      66 URIs      59 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-16367-8_12 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nab3e8b2a104e479780fa820629fba31b
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description Property testing considers the task of testing rapidly (in particular, with very few samples into the data), if some massive data satisfies some given property, or is far from satisfying the property. For “global properties”, i.e., properties that really depend somewhat on every piece of the data, one could ask how it can be tested by so few samples? We suggest that for “natural” properties, this should happen because the property is invariant under “nice” set of “relabellings” of the data. We refer to this set of relabellings as the “invariance class” of the property and advocate explicit identification of the invariance class of locally testable properties. Our hope is the explicit knowledge of the invariance class may lead to more general, broader, results.After pointing out the invariance classes associated with some the basic classes of testable properties, we focus on “algebraic properties” which seem to be characterized by the fact that the properties are themselves vector spaces, while their domains are also vector spaces and the properties are invariant under affine transformations of the domain. We survey recent results (obtained with Tali Kaufman, Elena Grigorescu and Eli Ben-Sasson) that give broad conditions that are sufficient for local testability among this class of properties, and some structural theorems that attempt to describe which properties exhibit the sufficient conditions.
7 schema:editor Nf1b99b3b14f841f0b0c403e320faab76
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N7d764753c8a04e1e9881f308e2a2172c
12 schema:keywords affine transformation
13 algebraic properties
14 basic classes
15 broad conditions
16 class
17 class of properties
18 conditions
19 data
20 data satisfies
21 domain
22 explicit identification
23 explicit knowledge
24 fact
25 global properties
26 hope
27 identification
28 invariance
29 invariance classes
30 knowledge
31 local testability
32 pieces
33 properties
34 property testing
35 recent results
36 relabelling
37 results
38 samples
39 satisfies
40 set
41 space
42 structural theorem
43 sufficient conditions
44 task
45 task of testing
46 testability
47 testable properties
48 testing
49 theorem
50 transformation
51 vector space
52 schema:name Invariance in Property Testing
53 schema:pagination 211-227
54 schema:productId N3e2c02aa9cca4219aca640ac5208bd00
55 Ne1abac9347204ae2a662cd30087f5727
56 schema:publisher N9b0321d585334862ac9d48b588c3d62d
57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047100906
58 https://doi.org/10.1007/978-3-642-16367-8_12
59 schema:sdDatePublished 2022-05-10T10:54
60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
61 schema:sdPublisher N196688626ba743d8be10134b91497bde
62 schema:url https://doi.org/10.1007/978-3-642-16367-8_12
63 sgo:license sg:explorer/license/
64 sgo:sdDataset chapters
65 rdf:type schema:Chapter
66 N196688626ba743d8be10134b91497bde schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 N3e2c02aa9cca4219aca640ac5208bd00 schema:name dimensions_id
69 schema:value pub.1047100906
70 rdf:type schema:PropertyValue
71 N7d764753c8a04e1e9881f308e2a2172c schema:isbn 978-3-642-16366-1
72 978-3-642-16367-8
73 schema:name Property Testing
74 rdf:type schema:Book
75 N9b0321d585334862ac9d48b588c3d62d schema:name Springer Nature
76 rdf:type schema:Organisation
77 Na061b960375c4c0687080f93d760e8c7 schema:familyName Goldreich
78 schema:givenName Oded
79 rdf:type schema:Person
80 Nab3e8b2a104e479780fa820629fba31b rdf:first sg:person.014663420265.17
81 rdf:rest rdf:nil
82 Ne1abac9347204ae2a662cd30087f5727 schema:name doi
83 schema:value 10.1007/978-3-642-16367-8_12
84 rdf:type schema:PropertyValue
85 Nf1b99b3b14f841f0b0c403e320faab76 rdf:first Na061b960375c4c0687080f93d760e8c7
86 rdf:rest rdf:nil
87 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
88 schema:name Mathematical Sciences
89 rdf:type schema:DefinedTerm
90 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
91 schema:name Pure Mathematics
92 rdf:type schema:DefinedTerm
93 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.419815.0
94 schema:familyName Sudan
95 schema:givenName Madhu
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
97 rdf:type schema:Person
98 grid-institutes:grid.419815.0 schema:alternateName Microsoft Research New England, One Memorial Drive, 02142, Cambridge, MA, USA
99 schema:name Microsoft Research New England, One Memorial Drive, 02142, Cambridge, MA, USA
100 rdf:type schema:Organization
 




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


...