2010
AUTHORS ABSTRACTProperty 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... »
PAGES211-227
Property Testing
ISBN
978-3-642-16366-1
978-3-642-16367-8
http://scigraph.springernature.com/pub.10.1007/978-3-642-16367-8_12
DOIhttp://dx.doi.org/10.1007/978-3-642-16367-8_12
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1047100906
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
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 |