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/None", 
          "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", 
      "massive data satisfies", 
      "set of relabellings"
    ], 
    "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-01-01T19:27", 
    "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_7.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.

102 TRIPLES      23 PREDICATES      68 URIs      61 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 N3457e669f83f4c26bf487e00598e1286
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 N8881bb98d4d543cba02cb3ac335202a2
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N2efc4b6766bf4e19923a4820316e3dac
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 massive data satisfies
33 pieces
34 properties
35 property testing
36 recent results
37 relabelling
38 results
39 samples
40 satisfies
41 set
42 set of relabellings
43 space
44 structural theorem
45 sufficient conditions
46 task
47 task of testing
48 testability
49 testable properties
50 testing
51 theorem
52 transformation
53 vector space
54 schema:name Invariance in Property Testing
55 schema:pagination 211-227
56 schema:productId N16f98a742a1d4bb3a3f609218aff088b
57 N4efa25dbccf44cf794319649eaaa1da8
58 schema:publisher N3e2bcef6fd1c4127814e893db52c3641
59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047100906
60 https://doi.org/10.1007/978-3-642-16367-8_12
61 schema:sdDatePublished 2022-01-01T19:27
62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
63 schema:sdPublisher N68b7bfaaf8e548b6962285eab75f2e23
64 schema:url https://doi.org/10.1007/978-3-642-16367-8_12
65 sgo:license sg:explorer/license/
66 sgo:sdDataset chapters
67 rdf:type schema:Chapter
68 N16f98a742a1d4bb3a3f609218aff088b schema:name dimensions_id
69 schema:value pub.1047100906
70 rdf:type schema:PropertyValue
71 N2efc4b6766bf4e19923a4820316e3dac schema:isbn 978-3-642-16366-1
72 978-3-642-16367-8
73 schema:name Property Testing
74 rdf:type schema:Book
75 N3457e669f83f4c26bf487e00598e1286 rdf:first sg:person.014663420265.17
76 rdf:rest rdf:nil
77 N3e2bcef6fd1c4127814e893db52c3641 schema:name Springer Nature
78 rdf:type schema:Organisation
79 N4efa25dbccf44cf794319649eaaa1da8 schema:name doi
80 schema:value 10.1007/978-3-642-16367-8_12
81 rdf:type schema:PropertyValue
82 N68b7bfaaf8e548b6962285eab75f2e23 schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 N8881bb98d4d543cba02cb3ac335202a2 rdf:first Nb44e0e37b716421293d2ac19a8f596a0
85 rdf:rest rdf:nil
86 Nb44e0e37b716421293d2ac19a8f596a0 schema:familyName Goldreich
87 schema:givenName Oded
88 rdf:type schema:Person
89 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
90 schema:name Mathematical Sciences
91 rdf:type schema:DefinedTerm
92 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
93 schema:name Pure Mathematics
94 rdf:type schema:DefinedTerm
95 sg:person.014663420265.17 schema:affiliation grid-institutes:None
96 schema:familyName Sudan
97 schema:givenName Madhu
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
99 rdf:type schema:Person
100 grid-institutes:None schema:alternateName Microsoft Research New England, One Memorial Drive, 02142, Cambridge, MA, USA
101 schema:name Microsoft Research New England, One Memorial Drive, 02142, Cambridge, MA, USA
102 rdf:type schema:Organization
 




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


...