Limits on the Rate of Locally Testable Affine-Invariant Codes View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Eli Ben-Sasson , Madhu Sudan

ABSTRACT

Despite its many applications, to program checking, probabilistically checkable proofs, locally testable and locally decodable codes, and cryptography, “algebraic property testing” is not well-understood. A significant obstacle to a better understanding, was a lack of a concrete definition that abstracted known testable algebraic properties and reflected their testability. This obstacle was removed by [Kaufman and Sudan, STOC 2008] who considered (linear) “affine-invariant properties”, i.e., properties that are closed under summation, and under affine transformations of the domain. Kaufman and Sudan showed that these two features (linearity of the property and its affine-invariance) play a central role in the testability of many known algebraic properties. However their work does not give a complete characterization of the testability of affine-invariant properties, and several technical obstacles need to be overcome to obtain such a characterization. Indeed, their work left open the tantalizing possibility that locally testable codes of rate dramatically better than that of the family of Reed-Muller codes (the most popular form of locally testable codes, which also happen to be affine-invariant) could be found by systematically exploring the space of affine-invariant properties.In this work we rule out this possibility and show that general (linear) affine-invariant properties are contained in Reed-Muller codes that are testable with a slightly larger query complexity. A central impediment to proving such results was the limited understanding of the structural restrictions on affine-invariant properties imposed by the existence of local tests. We manage to overcome this limitation and present a clean restriction satisfied by affine-invariant properties that exhibit local tests. We do so by relating the problem to that of studying the set of solutions of a certain nice class of (uniform, homogenous, diagonal) systems of multivariate polynomial equations. Our main technical result completely characterizes (combinatorially) the set of zeroes, or algebraic set, of such systems. More... »

PAGES

412-423

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_35

DOI

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

DIMENSIONS

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


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": [
      {
        "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": "Sudan", 
        "givenName": "Madhu", 
        "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": "Despite its many applications, to program checking, probabilistically checkable proofs, locally testable and locally decodable codes, and cryptography, \u201calgebraic property testing\u201d is not well-understood. A significant obstacle to a better understanding, was a lack of a concrete definition that abstracted known testable algebraic properties and reflected their testability. This obstacle was removed by [Kaufman and Sudan, STOC 2008] who considered (linear) \u201caffine-invariant properties\u201d, i.e., properties that are closed under summation, and under affine transformations of the domain. Kaufman and Sudan showed that these two features (linearity of the property and its affine-invariance) play a central role in the testability of many known algebraic properties. However their work does not give a complete characterization of the testability of affine-invariant properties, and several technical obstacles need to be overcome to obtain such a characterization. Indeed, their work left open the tantalizing possibility that locally testable codes of rate dramatically better than that of the family of Reed-Muller codes (the most popular form of locally testable codes, which also happen to be affine-invariant) could be found by systematically exploring the space of affine-invariant properties.In this work we rule out this possibility and show that general (linear) affine-invariant properties are contained in Reed-Muller codes that are testable with a slightly larger query complexity. A central impediment to proving such results was the limited understanding of the structural restrictions on affine-invariant properties imposed by the existence of local tests. We manage to overcome this limitation and present a clean restriction satisfied by affine-invariant properties that exhibit local tests. We do so by relating the problem to that of studying the set of solutions of a certain nice class of (uniform, homogenous, diagonal) systems of multivariate polynomial equations. Our main technical result completely characterizes (combinatorially) the set of zeroes, or algebraic set, of such systems.", 
    "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_35", 
    "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": [
      "Reed-Muller codes", 
      "algebraic property testing", 
      "algebraic properties", 
      "program checking", 
      "checkable proofs", 
      "query complexity", 
      "set of solutions", 
      "multivariate polynomial equations", 
      "main technical result", 
      "set of zeros", 
      "decodable codes", 
      "affine transformation", 
      "nice class", 
      "polynomial equation", 
      "algebraic set", 
      "such systems", 
      "code", 
      "concrete definition", 
      "testability", 
      "affine-invariant properties", 
      "affine-invariant codes", 
      "checking", 
      "cryptography", 
      "obstacles", 
      "complete characterization", 
      "technical obstacles", 
      "testable codes", 
      "structural restrictions", 
      "local tests", 
      "set", 
      "technical results", 
      "property testing", 
      "significant obstacle", 
      "work", 
      "complexity", 
      "central impediment", 
      "Such results", 
      "system", 
      "equations", 
      "zeros", 
      "applications", 
      "proof", 
      "domain", 
      "features", 
      "tantalizing possibility", 
      "space", 
      "existence", 
      "problem", 
      "solution", 
      "class", 
      "definition", 
      "properties", 
      "summation", 
      "results", 
      "restriction", 
      "limitations", 
      "testing", 
      "transformation", 
      "possibility", 
      "impediments", 
      "limit", 
      "better understanding", 
      "understanding", 
      "lack", 
      "Kaufman", 
      "family", 
      "limited understanding", 
      "central role", 
      "rate", 
      "test", 
      "role", 
      "characterization", 
      "Sudan", 
      "testable algebraic properties", 
      "general (linear) affine-invariant properties", 
      "larger query complexity", 
      "clean restriction", 
      "certain nice class", 
      "Testable Affine-Invariant Codes"
    ], 
    "name": "Limits on the Rate of Locally Testable Affine-Invariant Codes", 
    "pagination": "412-423", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1036468604"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-22935-0_35"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-22935-0_35", 
      "https://app.dimensions.ai/details/publication/pub.1036468604"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:21", 
    "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_367.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-22935-0_35"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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


 

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

156 TRIPLES      23 PREDICATES      105 URIs      98 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-22935-0_35 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Ndebf877a7efe4cb589605b26b48570e9
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description Despite its many applications, to program checking, probabilistically checkable proofs, locally testable and locally decodable codes, and cryptography, “algebraic property testing” is not well-understood. A significant obstacle to a better understanding, was a lack of a concrete definition that abstracted known testable algebraic properties and reflected their testability. This obstacle was removed by [Kaufman and Sudan, STOC 2008] who considered (linear) “affine-invariant properties”, i.e., properties that are closed under summation, and under affine transformations of the domain. Kaufman and Sudan showed that these two features (linearity of the property and its affine-invariance) play a central role in the testability of many known algebraic properties. However their work does not give a complete characterization of the testability of affine-invariant properties, and several technical obstacles need to be overcome to obtain such a characterization. Indeed, their work left open the tantalizing possibility that locally testable codes of rate dramatically better than that of the family of Reed-Muller codes (the most popular form of locally testable codes, which also happen to be affine-invariant) could be found by systematically exploring the space of affine-invariant properties.In this work we rule out this possibility and show that general (linear) affine-invariant properties are contained in Reed-Muller codes that are testable with a slightly larger query complexity. A central impediment to proving such results was the limited understanding of the structural restrictions on affine-invariant properties imposed by the existence of local tests. We manage to overcome this limitation and present a clean restriction satisfied by affine-invariant properties that exhibit local tests. We do so by relating the problem to that of studying the set of solutions of a certain nice class of (uniform, homogenous, diagonal) systems of multivariate polynomial equations. Our main technical result completely characterizes (combinatorially) the set of zeroes, or algebraic set, of such systems.
7 schema:editor N1ff384cc0ff948f09bf7f2324ce55dc8
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N5fbff628acb145d5974a95ebceaf6dcf
12 schema:keywords Kaufman
13 Reed-Muller codes
14 Such results
15 Sudan
16 Testable Affine-Invariant Codes
17 affine transformation
18 affine-invariant codes
19 affine-invariant properties
20 algebraic properties
21 algebraic property testing
22 algebraic set
23 applications
24 better understanding
25 central impediment
26 central role
27 certain nice class
28 characterization
29 checkable proofs
30 checking
31 class
32 clean restriction
33 code
34 complete characterization
35 complexity
36 concrete definition
37 cryptography
38 decodable codes
39 definition
40 domain
41 equations
42 existence
43 family
44 features
45 general (linear) affine-invariant properties
46 impediments
47 lack
48 larger query complexity
49 limit
50 limitations
51 limited understanding
52 local tests
53 main technical result
54 multivariate polynomial equations
55 nice class
56 obstacles
57 polynomial equation
58 possibility
59 problem
60 program checking
61 proof
62 properties
63 property testing
64 query complexity
65 rate
66 restriction
67 results
68 role
69 set
70 set of solutions
71 set of zeros
72 significant obstacle
73 solution
74 space
75 structural restrictions
76 such systems
77 summation
78 system
79 tantalizing possibility
80 technical obstacles
81 technical results
82 test
83 testability
84 testable algebraic properties
85 testable codes
86 testing
87 transformation
88 understanding
89 work
90 zeros
91 schema:name Limits on the Rate of Locally Testable Affine-Invariant Codes
92 schema:pagination 412-423
93 schema:productId N09b46baab7784a849d292880aaa2cb93
94 N1f3eee5ad83240cba88b5a1883cbd933
95 schema:publisher Ne4ac74e0666d4c898a77f4d1a303880d
96 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036468604
97 https://doi.org/10.1007/978-3-642-22935-0_35
98 schema:sdDatePublished 2022-01-01T19:21
99 schema:sdLicense https://scigraph.springernature.com/explorer/license/
100 schema:sdPublisher Na545f62083cc4ccf80f575f8bfc1992b
101 schema:url https://doi.org/10.1007/978-3-642-22935-0_35
102 sgo:license sg:explorer/license/
103 sgo:sdDataset chapters
104 rdf:type schema:Chapter
105 N047b748516624ef1b076af9fa9d17afd schema:familyName Rolim
106 schema:givenName José D. P.
107 rdf:type schema:Person
108 N09b46baab7784a849d292880aaa2cb93 schema:name doi
109 schema:value 10.1007/978-3-642-22935-0_35
110 rdf:type schema:PropertyValue
111 N0f9b8e2ef3af412fb95175a5b0f3eb88 rdf:first N23745095b8b44cef8a84adc0629e4534
112 rdf:rest Nff540ecba9d149699d1945188704f280
113 N1f3eee5ad83240cba88b5a1883cbd933 schema:name dimensions_id
114 schema:value pub.1036468604
115 rdf:type schema:PropertyValue
116 N1ff384cc0ff948f09bf7f2324ce55dc8 rdf:first N3fa1060361704a49a5042fa893d38be7
117 rdf:rest N0f9b8e2ef3af412fb95175a5b0f3eb88
118 N23745095b8b44cef8a84adc0629e4534 schema:familyName Jansen
119 schema:givenName Klaus
120 rdf:type schema:Person
121 N3fa1060361704a49a5042fa893d38be7 schema:familyName Goldberg
122 schema:givenName Leslie Ann
123 rdf:type schema:Person
124 N5fbff628acb145d5974a95ebceaf6dcf schema:isbn 978-3-642-22934-3
125 978-3-642-22935-0
126 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
127 rdf:type schema:Book
128 N8df7a4a9466340e8b59f92ed1e30cafd rdf:first N047b748516624ef1b076af9fa9d17afd
129 rdf:rest rdf:nil
130 Na545f62083cc4ccf80f575f8bfc1992b schema:name Springer Nature - SN SciGraph project
131 rdf:type schema:Organization
132 Nb2bdf90f18ca471d986fa86297467bf8 schema:familyName Ravi
133 schema:givenName R.
134 rdf:type schema:Person
135 Ndebf877a7efe4cb589605b26b48570e9 rdf:first sg:person.014331106007.34
136 rdf:rest Nfb7403f44898439983b814d354bc3ede
137 Ne4ac74e0666d4c898a77f4d1a303880d schema:name Springer Nature
138 rdf:type schema:Organisation
139 Nfb7403f44898439983b814d354bc3ede rdf:first sg:person.014663420265.17
140 rdf:rest rdf:nil
141 Nff540ecba9d149699d1945188704f280 rdf:first Nb2bdf90f18ca471d986fa86297467bf8
142 rdf:rest N8df7a4a9466340e8b59f92ed1e30cafd
143 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
144 schema:name Mathematical Sciences
145 rdf:type schema:DefinedTerm
146 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
147 schema:name Pure Mathematics
148 rdf:type schema:DefinedTerm
149 sg:person.014331106007.34 schema:familyName Ben-Sasson
150 schema:givenName Eli
151 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014331106007.34
152 rdf:type schema:Person
153 sg:person.014663420265.17 schema:familyName Sudan
154 schema:givenName Madhu
155 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
156 rdf:type schema:Person
 




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


...