# On Sums of Locally Testable Affine Invariant Properties

Ontology type: schema:Chapter      Open Access: True

### Chapter Info

DATE

2011

AUTHORS ABSTRACT

Affine-invariant properties are an abstract class of properties that generalize some central algebraic ones, such as linearity and low-degree-ness, that have been studied extensively in the context of property testing. Affine invariant properties consider functions mapping a big field \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_{q^n}$\end{document} to the subfield \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_q$\end{document} and include all properties that form an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_q$\end{document}-vector space and are invariant under affine transformations of the domain. Almost all the known locally testable affine-invariant properties have so-called “single-orbit characterizations” — namely they are specified by a single local constraint on the property, and the “orbit” of this constraint, i.e., translations of this constraint induced by affine-invariance. Single-orbit characterizations by a local constraint are also known to imply local testability. In this work we show that properties with single-orbit characterizations are closed under “summation”. To complement this result, we also show that the property of being an n-variate low-degree polynomial over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_q$\end{document} has a single-orbit characterization (even when the domain is viewed as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_{q^n}$\end{document} and so has very few affine transformations). As a consequence we find that the sum of any sparse affine-invariant property (properties satisfied by qO(n)-functions) with the set of degree d multivariate polynomials over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_q$\end{document} has a single-orbit characterization (and is hence locally testable) when q is prime. We conclude with some intriguing questions/conjectures attempting to classify all locally testable affine-invariant properties. More... »

PAGES

400-411

### Book

TITLE

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-642-22934-3
978-3-642-22935-0

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-22935-0_34

DOI

http://dx.doi.org/10.1007/978-3-642-22935-0_34

DIMENSIONS

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

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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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": [
{
"familyName": "Ben-Sasson",
"givenName": "Eli",
"id": "sg:person.014331106007.34",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014331106007.34"
],
"type": "Person"
},
{
"familyName": "Grigorescu",
"givenName": "Elena",
"id": "sg:person.014612515147.15",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014612515147.15"
],
"type": "Person"
},
{
"familyName": "Maatouk",
"givenName": "Ghid",
"id": "sg:person.012265023371.26",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012265023371.26"
],
"type": "Person"
},
{
"familyName": "Shpilka",
"givenName": "Amir",
"id": "sg:person.010556352637.70",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010556352637.70"
],
"type": "Person"
},
{
"familyName": "Sudan",
"id": "sg:person.014663420265.17",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17"
],
"type": "Person"
}
],
"datePublished": "2011",
"datePublishedReg": "2011-01-01",
"description": "Affine-invariant properties are an abstract class of properties that generalize some central algebraic ones, such as linearity and low-degree-ness, that have been studied extensively in the context of property testing. Affine invariant properties consider functions mapping a big field \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathbb{F}_{q^n}$\\end{document} to the subfield \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathbb{F}_q$\\end{document} and include all properties that form an \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathbb{F}_q$\\end{document}-vector space and are invariant under affine transformations of the domain. Almost all the known locally testable affine-invariant properties have so-called \u201csingle-orbit characterizations\u201d \u2014 namely they are specified by a single local constraint on the property, and the \u201corbit\u201d of this constraint, i.e., translations of this constraint induced by affine-invariance. Single-orbit characterizations by a local constraint are also known to imply local testability. In this work we show that properties with single-orbit characterizations are closed under \u201csummation\u201d. To complement this result, we also show that the property of being an n-variate low-degree polynomial over \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathbb{F}_q$\\end{document} has a single-orbit characterization (even when the domain is viewed as \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathbb{F}_{q^n}$\\end{document} and so has very few affine transformations). As a consequence we find that the sum of any sparse affine-invariant property (properties satisfied by qO(n)-functions) with the set of degree d multivariate polynomials over \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathbb{F}_q$\\end{document} has a single-orbit characterization (and is hence locally testable) when q is prime. We conclude with some intriguing questions/conjectures attempting to classify all locally testable affine-invariant properties.",
"editor": [
{
"familyName": "Goldberg",
"givenName": "Leslie Ann",
"type": "Person"
},
{
"familyName": "Jansen",
"givenName": "Klaus",
"type": "Person"
},
{
"familyName": "Ravi",
"givenName": "R.",
"type": "Person"
},
{
"familyName": "Rolim",
"givenName": "Jos\u00e9 D. P.",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-22935-0_34",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-642-22934-3",
"978-3-642-22935-0"
],
"name": "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques",
"type": "Book"
},
"keywords": [
"properties",
"linearity",
"invariant properties",
"big field",
"field",
"space",
"characterization",
"local constraints",
"constraints",
"orbit",
"summation",
"sum",
"affine-invariant properties",
"abstract classes",
"class",
"algebraic one",
"one",
"ness",
"context",
"property testing",
"testing",
"function",
"subfields",
"vector space",
"affine transformation",
"transformation",
"domain",
"translation",
"testability",
"work",
"results",
"low-degree polynomials",
"polynomials",
"consequences",
"set",
"multivariate polynomials",
"conjecture",
"central algebraic ones",
"testable affine-invariant properties",
"single-orbit characterizations",
"single local constraint",
"local testability",
"variate low-degree polynomial",
"sparse affine-invariant property",
"degree d multivariate polynomials",
"d multivariate polynomials",
"intriguing questions/conjectures",
"questions/conjectures"
],
"name": "On Sums of Locally Testable Affine Invariant Properties",
"pagination": "400-411",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1049575323"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-22935-0_34"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-22935-0_34",
"https://app.dimensions.ai/details/publication/pub.1049575323"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-01-01T19:27",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_75.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-22935-0_34"
}
]

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-22935-0_34'

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-22935-0_34'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22935-0_34'

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-22935-0_34'

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

143 TRIPLES      23 PREDICATES      74 URIs      67 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0101
3 schema:author N872d47693cfa4fdeb3f6d4895a92fa67
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description Affine-invariant properties are an abstract class of properties that generalize some central algebraic ones, such as linearity and low-degree-ness, that have been studied extensively in the context of property testing. Affine invariant properties consider functions mapping a big field \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_{q^n}$\end{document} to the subfield \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_q$\end{document} and include all properties that form an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_q$\end{document}-vector space and are invariant under affine transformations of the domain. Almost all the known locally testable affine-invariant properties have so-called “single-orbit characterizations” — namely they are specified by a single local constraint on the property, and the “orbit” of this constraint, i.e., translations of this constraint induced by affine-invariance. Single-orbit characterizations by a local constraint are also known to imply local testability. In this work we show that properties with single-orbit characterizations are closed under “summation”. To complement this result, we also show that the property of being an n-variate low-degree polynomial over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_q$\end{document} has a single-orbit characterization (even when the domain is viewed as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_{q^n}$\end{document} and so has very few affine transformations). As a consequence we find that the sum of any sparse affine-invariant property (properties satisfied by qO(n)-functions) with the set of degree d multivariate polynomials over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_q$\end{document} has a single-orbit characterization (and is hence locally testable) when q is prime. We conclude with some intriguing questions/conjectures attempting to classify all locally testable affine-invariant properties.
7 schema:editor Nfded2505680b47359c707eebd79ae1cc
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N9b497f3da9c54b3bbc81e0bc206f6fa7
12 schema:keywords abstract classes
13 affine transformation
14 affine-invariant properties
15 algebraic one
16 big field
17 central algebraic ones
18 characterization
19 class
20 conjecture
21 consequences
22 constraints
23 context
24 d multivariate polynomials
25 degree d multivariate polynomials
26 domain
27 field
28 function
29 intriguing questions/conjectures
30 invariant properties
31 linearity
32 local constraints
33 local testability
34 low-degree polynomials
35 multivariate polynomials
36 ness
37 one
38 orbit
39 polynomials
40 properties
41 property testing
42 questions/conjectures
43 results
44 set
45 single local constraint
46 single-orbit characterizations
47 space
48 sparse affine-invariant property
49 subfields
50 sum
51 summation
52 testability
53 testable affine-invariant properties
54 testing
55 transformation
56 translation
57 variate low-degree polynomial
58 vector space
59 work
60 schema:name On Sums of Locally Testable Affine Invariant Properties
61 schema:pagination 400-411
62 schema:productId N948a9d15ffac40969c3505c619fe2474
63 Ne5a190b433bb4877806514d101d81807
64 schema:publisher N81879497c34c4f76be666e04133dcdbc
65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049575323
66 https://doi.org/10.1007/978-3-642-22935-0_34
67 schema:sdDatePublished 2022-01-01T19:27
69 schema:sdPublisher Nb80af15acc3d4bc094a775d0d681d14a
70 schema:url https://doi.org/10.1007/978-3-642-22935-0_34
72 sgo:sdDataset chapters
73 rdf:type schema:Chapter
75 schema:givenName R.
76 rdf:type schema:Person
78 schema:givenName Leslie Ann
79 rdf:type schema:Person
80 N5991f799b1f94dcf8e1f672a0113fc02 rdf:first sg:person.014663420265.17
81 rdf:rest rdf:nil
83 schema:givenName Klaus
84 rdf:type schema:Person
85 N5c0e3493ff6f4b5bb171c28c4d0e5b67 schema:familyName Rolim
86 schema:givenName José D. P.
87 rdf:type schema:Person
88 N746db415ecc146248269b204d92982ee rdf:first sg:person.012265023371.26
89 rdf:rest Nde3b61d71c0c4eea868ba56268a37cf3
90 N81879497c34c4f76be666e04133dcdbc schema:name Springer Nature
91 rdf:type schema:Organisation
92 N872d47693cfa4fdeb3f6d4895a92fa67 rdf:first sg:person.014331106007.34
93 rdf:rest Nd25b64ba33e04b4c9a9f88b12972e862
94 N948a9d15ffac40969c3505c619fe2474 schema:name doi
95 schema:value 10.1007/978-3-642-22935-0_34
96 rdf:type schema:PropertyValue
97 N9b497f3da9c54b3bbc81e0bc206f6fa7 schema:isbn 978-3-642-22934-3
98 978-3-642-22935-0
99 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
100 rdf:type schema:Book
101 Nb80af15acc3d4bc094a775d0d681d14a schema:name Springer Nature - SN SciGraph project
102 rdf:type schema:Organization
103 Nd25b64ba33e04b4c9a9f88b12972e862 rdf:first sg:person.014612515147.15
104 rdf:rest N746db415ecc146248269b204d92982ee
105 Nd34f116dc35149d4b730fa7390b33798 rdf:first N5c0e3493ff6f4b5bb171c28c4d0e5b67
106 rdf:rest rdf:nil
107 Nde3b61d71c0c4eea868ba56268a37cf3 rdf:first sg:person.010556352637.70
108 rdf:rest N5991f799b1f94dcf8e1f672a0113fc02
110 rdf:rest Nd34f116dc35149d4b730fa7390b33798
111 Ne5a190b433bb4877806514d101d81807 schema:name dimensions_id
112 schema:value pub.1049575323
113 rdf:type schema:PropertyValue
115 rdf:rest Ne38d343f53514f368b3ba1311540545b
117 rdf:rest Nf619e006044f45e5ab01608780c4d4ce
118 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
119 schema:name Mathematical Sciences
120 rdf:type schema:DefinedTerm
121 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
122 schema:name Pure Mathematics
123 rdf:type schema:DefinedTerm
124 sg:person.010556352637.70 schema:familyName Shpilka
125 schema:givenName Amir
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010556352637.70
127 rdf:type schema:Person
128 sg:person.012265023371.26 schema:familyName Maatouk
129 schema:givenName Ghid
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012265023371.26
131 rdf:type schema:Person
132 sg:person.014331106007.34 schema:familyName Ben-Sasson
133 schema:givenName Eli
134 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014331106007.34
135 rdf:type schema:Person
136 sg:person.014612515147.15 schema:familyName Grigorescu
137 schema:givenName Elena
138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014612515147.15
139 rdf:type schema:Person
140 sg:person.014663420265.17 schema:familyName Sudan