Absolutely Sound Testing of Lifted Codes View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Elad Haramaty , Noga Ron-Zewi , Madhu Sudan

ABSTRACT

In this work we present a strong analysis of the testability of a broad, and to date the most interesting known, class of “affine-invariant” codes. Affine-invariant codes are codes whose coordinates are associated with a vector space and are invariant under affine transformations of the coordinate space. Affine-invariant linear codes form a natural abstraction of algebraic properties such as linearity and low-degree, which have been of significant interest in theoretical computer science in the past. The study of affine-invariance is motivated in part by its relationship to property testing: Affine-invariant linear codes tend to be locally testable under fairly minimal and almost necessary conditions.Recent works by Ben-Sasson et al. (CCC 2011) and Guo et al. (ITCS 2013) have introduced a new class of affine-invariant linear codes based on an operation called “lifting”. Given a base code over a t-dimensional space, its m-dimensional lift consists of all words whose restriction to every t-dimensional affine subspace is a codeword of the base code. Lifting not only captures the most familiar codes, which can be expressed as lifts of low-degree polynomials, it also yields new codes when lifting “medium-degree” polynomials whose rate is better than that of corresponding polynomial codes, and all other combinatorial qualities are no worse.In this work we show that codes derived from lifting are also testable in an “absolutely sound” way. Specifically, we consider the natural test: Pick a random affine subspace of base dimension and verify that a given word is a codeword of the base code when restricted to the chosen subspace. We show that this test accepts codewords with probability one, while rejecting words at constant distance from the code with constant probability (depending only on the alphabet size). This work thus extends the results of Bhattacharyya et al. (FOCS 2010) and Haramaty et al. (FOCS 2011), while giving concrete new codes of higher rate that have absolutely sound testers. In particular we show that there exists codes satisfying the requirements of Barak et al. (FOCS 2012) to construct small set expanders with a large number of eigenvalues close to the maximal one, with rate slightly higher than the ones used in their work. More... »

PAGES

671-682

Book

TITLE

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-642-40327-9
978-3-642-40328-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-40328-6_46

DOI

http://dx.doi.org/10.1007/978-3-642-40328-6_46

DIMENSIONS

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


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": "Department of Computer Science, Technion, Haifa, Israel", 
          "id": "http://www.grid.ac/institutes/grid.6451.6", 
          "name": [
            "Department of Computer Science, Technion, Haifa, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Haramaty", 
        "givenName": "Elad", 
        "id": "sg:person.015752347745.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015752347745.78"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Technion, Haifa, Israel", 
          "id": "http://www.grid.ac/institutes/grid.6451.6", 
          "name": [
            "Department of Computer Science, Technion, Haifa, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ron-Zewi", 
        "givenName": "Noga", 
        "id": "sg:person.013153216765.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013153216765.32"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Microsoft Research New England, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Microsoft Research New England, 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": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "In this work we present a strong analysis of the testability of a broad, and to date the most interesting known, class of \u201caffine-invariant\u201d codes. Affine-invariant codes are codes whose coordinates are associated with a vector space and are invariant under affine transformations of the coordinate space. Affine-invariant linear codes form a natural abstraction of algebraic properties such as linearity and low-degree, which have been of significant interest in theoretical computer science in the past. The study of affine-invariance is motivated in part by its relationship to property testing: Affine-invariant linear codes tend to be locally testable under fairly minimal and almost necessary conditions.Recent works by Ben-Sasson et al. (CCC 2011) and Guo et al. (ITCS 2013) have introduced a new class of affine-invariant linear codes based on an operation called \u201clifting\u201d. Given a base code over a t-dimensional space, its m-dimensional lift consists of all words whose restriction to every t-dimensional affine subspace is a codeword of the base code. Lifting not only captures the most familiar codes, which can be expressed as lifts of low-degree polynomials, it also yields new codes when lifting \u201cmedium-degree\u201d polynomials whose rate is better than that of corresponding polynomial codes, and all other combinatorial qualities are no worse.In this work we show that codes derived from lifting are also testable in an \u201cabsolutely sound\u201d way. Specifically, we consider the natural test: Pick a random affine subspace of base dimension and verify that a given word is a codeword of the base code when restricted to the chosen subspace. We show that this test accepts codewords with probability one, while rejecting words at constant distance from the code with constant probability (depending only on the alphabet size). This work thus extends the results of Bhattacharyya et al. (FOCS 2010) and Haramaty et al. (FOCS 2011), while giving concrete new codes of higher rate that have absolutely sound testers. In particular we show that there exists codes satisfying the requirements of Barak et al. (FOCS 2012) to construct small set expanders with a large number of eigenvalues close to the maximal one, with rate slightly higher than the ones used in their work.", 
    "editor": [
      {
        "familyName": "Raghavendra", 
        "givenName": "Prasad", 
        "type": "Person"
      }, 
      {
        "familyName": "Raskhodnikova", 
        "givenName": "Sofya", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-40328-6_46", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-40327-9", 
        "978-3-642-40328-6"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "linear codes", 
      "affine subspace", 
      "theoretical computer science", 
      "low-degree polynomials", 
      "dimensional affine subspace", 
      "algebraic properties", 
      "probability one", 
      "vector space", 
      "dimensional space", 
      "affine-invariant codes", 
      "new code", 
      "necessary condition", 
      "subspace", 
      "polynomial codes", 
      "coordinate space", 
      "constant probability", 
      "computer science", 
      "polynomials", 
      "natural abstraction", 
      "strong analysis", 
      "space", 
      "et al", 
      "affine transformation", 
      "class", 
      "base code", 
      "Guo et al", 
      "new class", 
      "codewords", 
      "natural test", 
      "eigenvalues", 
      "Bhattacharyya", 
      "large number", 
      "code", 
      "recent work", 
      "coordinates", 
      "probability", 
      "property testing", 
      "lift", 
      "one", 
      "constant distance", 
      "lifting", 
      "work", 
      "significant interest", 
      "dimensions", 
      "transformation", 
      "al", 
      "restriction", 
      "operation", 
      "number", 
      "properties", 
      "science", 
      "conditions", 
      "abstraction", 
      "way", 
      "requirements", 
      "interest", 
      "results", 
      "analysis", 
      "distance", 
      "expander", 
      "linearity", 
      "part", 
      "words", 
      "rate", 
      "test", 
      "quality", 
      "testability", 
      "past", 
      "testing", 
      "relationship", 
      "study", 
      "date", 
      "Ben-Sasson et al", 
      "tester", 
      "high rate", 
      "Barak et al", 
      "familiar code", 
      "sound testing", 
      "base dimensions", 
      "Affine-invariant linear codes", 
      "dimensional lift", 
      "combinatorial quality", 
      "random affine subspace", 
      "results of Bhattacharyya", 
      "Haramaty et al", 
      "concrete new codes", 
      "sound testers", 
      "small set expanders", 
      "set expanders", 
      "Lifted Codes"
    ], 
    "name": "Absolutely Sound Testing of Lifted Codes", 
    "pagination": "671-682", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1038584680"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-40328-6_46"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-40328-6_46", 
      "https://app.dimensions.ai/details/publication/pub.1038584680"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:07", 
    "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_125.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-40328-6_46"
  }
]
 

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-40328-6_46'

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-40328-6_46'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-40328-6_46'

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-40328-6_46'


 

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

182 TRIPLES      23 PREDICATES      116 URIs      109 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-40328-6_46 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N254cbc0d5cac4ad4835475b5d1f87209
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description In this work we present a strong analysis of the testability of a broad, and to date the most interesting known, class of “affine-invariant” codes. Affine-invariant codes are codes whose coordinates are associated with a vector space and are invariant under affine transformations of the coordinate space. Affine-invariant linear codes form a natural abstraction of algebraic properties such as linearity and low-degree, which have been of significant interest in theoretical computer science in the past. The study of affine-invariance is motivated in part by its relationship to property testing: Affine-invariant linear codes tend to be locally testable under fairly minimal and almost necessary conditions.Recent works by Ben-Sasson et al. (CCC 2011) and Guo et al. (ITCS 2013) have introduced a new class of affine-invariant linear codes based on an operation called “lifting”. Given a base code over a t-dimensional space, its m-dimensional lift consists of all words whose restriction to every t-dimensional affine subspace is a codeword of the base code. Lifting not only captures the most familiar codes, which can be expressed as lifts of low-degree polynomials, it also yields new codes when lifting “medium-degree” polynomials whose rate is better than that of corresponding polynomial codes, and all other combinatorial qualities are no worse.In this work we show that codes derived from lifting are also testable in an “absolutely sound” way. Specifically, we consider the natural test: Pick a random affine subspace of base dimension and verify that a given word is a codeword of the base code when restricted to the chosen subspace. We show that this test accepts codewords with probability one, while rejecting words at constant distance from the code with constant probability (depending only on the alphabet size). This work thus extends the results of Bhattacharyya et al. (FOCS 2010) and Haramaty et al. (FOCS 2011), while giving concrete new codes of higher rate that have absolutely sound testers. In particular we show that there exists codes satisfying the requirements of Barak et al. (FOCS 2012) to construct small set expanders with a large number of eigenvalues close to the maximal one, with rate slightly higher than the ones used in their work.
7 schema:editor N81b94993cd1049f0825d04fc357d4e11
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N8f2c77d913304bc39da95ddf7d37da7d
12 schema:keywords Affine-invariant linear codes
13 Barak et al
14 Ben-Sasson et al
15 Bhattacharyya
16 Guo et al
17 Haramaty et al
18 Lifted Codes
19 abstraction
20 affine subspace
21 affine transformation
22 affine-invariant codes
23 al
24 algebraic properties
25 analysis
26 base code
27 base dimensions
28 class
29 code
30 codewords
31 combinatorial quality
32 computer science
33 concrete new codes
34 conditions
35 constant distance
36 constant probability
37 coordinate space
38 coordinates
39 date
40 dimensional affine subspace
41 dimensional lift
42 dimensional space
43 dimensions
44 distance
45 eigenvalues
46 et al
47 expander
48 familiar code
49 high rate
50 interest
51 large number
52 lift
53 lifting
54 linear codes
55 linearity
56 low-degree polynomials
57 natural abstraction
58 natural test
59 necessary condition
60 new class
61 new code
62 number
63 one
64 operation
65 part
66 past
67 polynomial codes
68 polynomials
69 probability
70 probability one
71 properties
72 property testing
73 quality
74 random affine subspace
75 rate
76 recent work
77 relationship
78 requirements
79 restriction
80 results
81 results of Bhattacharyya
82 science
83 set expanders
84 significant interest
85 small set expanders
86 sound testers
87 sound testing
88 space
89 strong analysis
90 study
91 subspace
92 test
93 testability
94 tester
95 testing
96 theoretical computer science
97 transformation
98 vector space
99 way
100 words
101 work
102 schema:name Absolutely Sound Testing of Lifted Codes
103 schema:pagination 671-682
104 schema:productId N85af5fbca5a34ecd845a170db2d43bde
105 N8c5489d9bfc6468bb711b418b636e71a
106 schema:publisher N659086046f05412d8dc976ca93426c3f
107 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038584680
108 https://doi.org/10.1007/978-3-642-40328-6_46
109 schema:sdDatePublished 2022-01-01T19:07
110 schema:sdLicense https://scigraph.springernature.com/explorer/license/
111 schema:sdPublisher N3b5209772fd2474587b3a22d937f8463
112 schema:url https://doi.org/10.1007/978-3-642-40328-6_46
113 sgo:license sg:explorer/license/
114 sgo:sdDataset chapters
115 rdf:type schema:Chapter
116 N03bfa0b1240d4f7485e4de3850fba9bf schema:familyName Jansen
117 schema:givenName Klaus
118 rdf:type schema:Person
119 N254cbc0d5cac4ad4835475b5d1f87209 rdf:first sg:person.015752347745.78
120 rdf:rest Nc446650da67e4894a1e97f5306ff78ac
121 N3b5209772fd2474587b3a22d937f8463 schema:name Springer Nature - SN SciGraph project
122 rdf:type schema:Organization
123 N659086046f05412d8dc976ca93426c3f schema:name Springer Nature
124 rdf:type schema:Organisation
125 N6912ab1b317146e184fa1e95c7af0fa4 rdf:first sg:person.014663420265.17
126 rdf:rest rdf:nil
127 N81b94993cd1049f0825d04fc357d4e11 rdf:first Nc2fb446e91b54de4b1583faea407b9ee
128 rdf:rest Ne125eaa79bf648a1a95f389a401723c9
129 N85af5fbca5a34ecd845a170db2d43bde schema:name dimensions_id
130 schema:value pub.1038584680
131 rdf:type schema:PropertyValue
132 N8c5489d9bfc6468bb711b418b636e71a schema:name doi
133 schema:value 10.1007/978-3-642-40328-6_46
134 rdf:type schema:PropertyValue
135 N8f2c77d913304bc39da95ddf7d37da7d schema:isbn 978-3-642-40327-9
136 978-3-642-40328-6
137 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
138 rdf:type schema:Book
139 N945512b3d1124d908ac9eb0b87f2c936 schema:familyName Rolim
140 schema:givenName José D. P.
141 rdf:type schema:Person
142 Nc2fb446e91b54de4b1583faea407b9ee schema:familyName Raghavendra
143 schema:givenName Prasad
144 rdf:type schema:Person
145 Nc446650da67e4894a1e97f5306ff78ac rdf:first sg:person.013153216765.32
146 rdf:rest N6912ab1b317146e184fa1e95c7af0fa4
147 Ncfa9c0e8e5464c75941517e3770cdb7a schema:familyName Raskhodnikova
148 schema:givenName Sofya
149 rdf:type schema:Person
150 Ne125eaa79bf648a1a95f389a401723c9 rdf:first Ncfa9c0e8e5464c75941517e3770cdb7a
151 rdf:rest Nf4a5d40f559f42fb8f83149b331a400c
152 Nf4a5d40f559f42fb8f83149b331a400c rdf:first N03bfa0b1240d4f7485e4de3850fba9bf
153 rdf:rest Nfdaeeda1554e4770b33cd6c4ddb11a27
154 Nfdaeeda1554e4770b33cd6c4ddb11a27 rdf:first N945512b3d1124d908ac9eb0b87f2c936
155 rdf:rest rdf:nil
156 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
157 schema:name Mathematical Sciences
158 rdf:type schema:DefinedTerm
159 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
160 schema:name Pure Mathematics
161 rdf:type schema:DefinedTerm
162 sg:person.013153216765.32 schema:affiliation grid-institutes:grid.6451.6
163 schema:familyName Ron-Zewi
164 schema:givenName Noga
165 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013153216765.32
166 rdf:type schema:Person
167 sg:person.014663420265.17 schema:affiliation grid-institutes:None
168 schema:familyName Sudan
169 schema:givenName Madhu
170 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
171 rdf:type schema:Person
172 sg:person.015752347745.78 schema:affiliation grid-institutes:grid.6451.6
173 schema:familyName Haramaty
174 schema:givenName Elad
175 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015752347745.78
176 rdf:type schema:Person
177 grid-institutes:None schema:alternateName Microsoft Research New England, Cambridge, MA, USA
178 schema:name Microsoft Research New England, Cambridge, MA, USA
179 rdf:type schema:Organization
180 grid-institutes:grid.6451.6 schema:alternateName Department of Computer Science, Technion, Haifa, Israel
181 schema:name Department of Computer Science, Technion, Haifa, Israel
182 rdf:type schema:Organization
 




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


...