# Corruption and Recovery-Efficient Locally Decodable Codes

Ontology type: schema:Chapter

### Chapter Info

DATE

2008-01-01

AUTHORS ABSTRACT

A (q, δ, ε)-locally decodable code (LDC)C: {0,1}n →{0,1}m is an encoding from n-bit strings to m-bit strings such that each bit xk can be recovered with probability at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{1}{2} + \epsilon$\end{document} from C(x) by a randomized algorithm that queries only q positions of C(x), even if up to δm positions of C(x) are corrupted. If C is a linear map, then the LDC is linear. We give improved constructions of LDCs in terms of the corruption parameter δ and recovery parameter ε. The key property of our LDCs is that they are non-linear, whereas all previous LDCs were linear.For any δ, ε ∈ [Ω(n− 1/2), O(1)], we give a family of (2, δ, ε)-LDCs with length . For linear (2, δ, ε)-LDCs, Obata has shown that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$m \geq \exp \left (\delta n \right )$\end{document}. Thus, for small enough constants δ, ε, two-query non-linear LDCs are shorter than two-query linear LDCs.We improve the dependence on δ and ε of all constant-query LDCs by providing general transformations to non-linear LDCs. Taking Yekhanin’s linear (3, δ, 1/2 − 6δ)-LDCs with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$m = \exp \left (n^{1/t} \right )$\end{document} for any prime of the form 2t − 1, we obtain non-linear (3, δ, ε)-LDCs with .Now consider a (q, δ, ε)-LDC C with a decoder that has n matchings M1, ..., Mn on the complete q-uniform hypergraph, whose vertices are identified with the positions of C(x). On input k ∈ [n] and received word y, the decoder chooses e = {a1, ..., aq} ∈ Mk uniformly at random and outputs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\bigoplus_{j=1}^q y_{a_j}$\end{document}. All known LDCs and ours have such a decoder, which we call a matching sum decoder. We show that if C is a two-query LDC with such a decoder, then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$m \geq \exp \left (\max(\delta, \epsilon)\delta n \right )$\end{document}. Interestingly, our techniques used here can further improve the dependence on δ of Yekhanin’s three-query LDCs. Namely, if δ ≥ 1/12 then Yekhanin’s three-query LDCs become trivial (have recovery probability less than half), whereas we obtain three-query LDCs of length \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\exp \left (n^{1/t} \right )$\end{document} for any prime of the form 2t − 1 with non-trivial recovery probability for any δ< 1/6. More... »

PAGES

584-595

### Book

TITLE

Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-540-85362-6
978-3-540-85363-3

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-85363-3_46

DOI

http://dx.doi.org/10.1007/978-3-540-85363-3_46

DIMENSIONS

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

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/11",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Medical and Health Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1103",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Clinical Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"id": "http://www.grid.ac/institutes/None",
"name": [
],
"type": "Organization"
},
"familyName": "Woodruff",
"givenName": "David",
"id": "sg:person.012727410605.86",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86"
],
"type": "Person"
}
],
"datePublished": "2008-01-01",
"datePublishedReg": "2008-01-01",
"description": "A (q, \u03b4, \u03b5)-locally decodable code (LDC)C: {0,1}n \u2192{0,1}m is an encoding from n-bit strings to m-bit strings such that each bit xk can be recovered with probability at least \\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}$\\frac{1}{2} + \\epsilon$\\end{document} from C(x) by a randomized algorithm that queries only q positions of C(x), even if up to \u03b4m positions of C(x) are corrupted. If C is a linear map, then the LDC is linear. We give improved constructions of LDCs in terms of the corruption parameter \u03b4 and recovery parameter \u03b5. The key property of our LDCs is that they are non-linear, whereas all previous LDCs were linear.For any \u03b4, \u03b5\u2009\u2208\u2009[\u03a9(n\u2212\u20091/2), O(1)], we give a family of (2, \u03b4, \u03b5)-LDCs with length . For linear (2, \u03b4, \u03b5)-LDCs, Obata has shown that \\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}$m \\geq \\exp \\left (\\delta n \\right )$\\end{document}. Thus, for small enough constants \u03b4, \u03b5, two-query non-linear LDCs are shorter than two-query linear LDCs.We improve the dependence on \u03b4 and \u03b5 of all constant-query LDCs by providing general transformations to non-linear LDCs. Taking Yekhanin\u2019s linear (3, \u03b4, 1/2\u2009\u2212\u20096\u03b4)-LDCs with \\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}$m = \\exp \\left (n^{1/t} \\right )$\\end{document} for any prime of the form 2t\u2009\u2212\u20091, we obtain non-linear (3, \u03b4, \u03b5)-LDCs with .Now consider a (q, \u03b4, \u03b5)-LDC C with a decoder that has n matchings M1, ..., Mn on the complete q-uniform hypergraph, whose vertices are identified with the positions of C(x). On input k\u2009\u2208\u2009[n] and received word y, the decoder chooses e\u2009=\u2009{a1, ..., aq}\u2009\u2208\u2009Mk uniformly at random and outputs \\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}$\\bigoplus_{j=1}^q y_{a_j}$\\end{document}. All known LDCs and ours have such a decoder, which we call a matching sum decoder. We show that if C is a two-query LDC with such a decoder, then \\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}$m \\geq \\exp \\left (\\max(\\delta, \\epsilon)\\delta n \\right )$\\end{document}. Interestingly, our techniques used here can further improve the dependence on \u03b4 of Yekhanin\u2019s three-query LDCs. Namely, if \u03b4\u2009\u2265\u20091/12 then Yekhanin\u2019s three-query LDCs become trivial (have recovery probability less than half), whereas we obtain three-query LDCs of length \\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}$\\exp \\left (n^{1/t} \\right )$\\end{document} for any prime of the form 2t\u2009\u2212\u20091 with non-trivial recovery probability for any \u03b4<\u20091/6.",
"editor": [
{
"familyName": "Goel",
"givenName": "Ashish",
"type": "Person"
},
{
"familyName": "Jansen",
"givenName": "Klaus",
"type": "Person"
},
{
"familyName": "Rolim",
"givenName": "Jos\u00e9 D. P.",
"type": "Person"
},
{
"familyName": "Rubinfeld",
"givenName": "Ronitt",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-540-85363-3_46",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-85362-6",
"978-3-540-85363-3"
],
"name": "Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques",
"type": "Book"
},
"keywords": [
"decodable codes",
"n-bit strings",
"string",
"bit strings",
"probability",
"randomized algorithm",
"Q positions",
"linear maps",
"improved construction",
"parameter \u03b4",
"parameter \u03b5",
"key properties",
"constants \u03b4",
"general transformation",
"linear",
"input k",
"word y",
"recovery probability",
"code",
"xk",
"algorithm",
"position",
"maps",
"construction",
"terms",
"properties",
"length",
"Obata",
"linear LDCs",
"dependence",
"transformation",
"primes",
"decoder",
"M1",
"hypergraphs",
"vertices",
"A1",
"output",
"ours",
"technique",
"Yekhanin",
"encoding",
"LDCs",
"family",
"Mn",
"corruption",
"Sum decoder"
],
"name": "Corruption and Recovery-Efficient Locally Decodable Codes",
"pagination": "584-595",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1016904024"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-540-85363-3_46"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-540-85363-3_46",
"https://app.dimensions.ai/details/publication/pub.1016904024"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-12-01T06:49",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_226.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-540-85363-3_46"
}
]

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-540-85363-3_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-540-85363-3_46'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-85363-3_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-540-85363-3_46'

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

121 TRIPLES      22 PREDICATES      71 URIs      64 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:1103
3 schema:author N1bd06d5198ea432b8a2455b559a854dd
4 schema:datePublished 2008-01-01
5 schema:datePublishedReg 2008-01-01
6 schema:description A (q, δ, ε)-locally decodable code (LDC)C: {0,1}n →{0,1}m is an encoding from n-bit strings to m-bit strings such that each bit xk can be recovered with probability at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{1}{2} + \epsilon$\end{document} from C(x) by a randomized algorithm that queries only q positions of C(x), even if up to δm positions of C(x) are corrupted. If C is a linear map, then the LDC is linear. We give improved constructions of LDCs in terms of the corruption parameter δ and recovery parameter ε. The key property of our LDCs is that they are non-linear, whereas all previous LDCs were linear.For any δ, ε ∈ [Ω(n− 1/2), O(1)], we give a family of (2, δ, ε)-LDCs with length . For linear (2, δ, ε)-LDCs, Obata has shown that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$m \geq \exp \left (\delta n \right )$\end{document}. Thus, for small enough constants δ, ε, two-query non-linear LDCs are shorter than two-query linear LDCs.We improve the dependence on δ and ε of all constant-query LDCs by providing general transformations to non-linear LDCs. Taking Yekhanin’s linear (3, δ, 1/2 − 6δ)-LDCs with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$m = \exp \left (n^{1/t} \right )$\end{document} for any prime of the form 2t − 1, we obtain non-linear (3, δ, ε)-LDCs with .Now consider a (q, δ, ε)-LDC C with a decoder that has n matchings M1, ..., Mn on the complete q-uniform hypergraph, whose vertices are identified with the positions of C(x). On input k ∈ [n] and received word y, the decoder chooses e = {a1, ..., aq} ∈ Mk uniformly at random and outputs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\bigoplus_{j=1}^q y_{a_j}$\end{document}. All known LDCs and ours have such a decoder, which we call a matching sum decoder. We show that if C is a two-query LDC with such a decoder, then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$m \geq \exp \left (\max(\delta, \epsilon)\delta n \right )$\end{document}. Interestingly, our techniques used here can further improve the dependence on δ of Yekhanin’s three-query LDCs. Namely, if δ ≥ 1/12 then Yekhanin’s three-query LDCs become trivial (have recovery probability less than half), whereas we obtain three-query LDCs of length \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\exp \left (n^{1/t} \right )$\end{document} for any prime of the form 2t − 1 with non-trivial recovery probability for any δ< 1/6.
7 schema:editor Nbf166d957e774ae0ac663f35a786692a
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Ncf2b6193558c479fa52149a6141a0468
11 schema:keywords A1
12 LDCs
13 M1
14 Mn
15 Obata
16 Q positions
17 Sum decoder
18 Yekhanin
19 algorithm
20 bit strings
21 code
22 constants δ
23 construction
24 corruption
25 decodable codes
26 decoder
27 dependence
28 encoding
29 family
30 general transformation
31 hypergraphs
32 improved construction
33 input k
34 key properties
35 length
36 linear
37 linear LDCs
38 linear maps
39 maps
40 n-bit strings
41 ours
42 output
43 parameter δ
44 parameter ε
45 position
46 primes
47 probability
48 properties
49 randomized algorithm
50 recovery probability
51 string
52 technique
53 terms
54 transformation
55 vertices
56 word y
57 xk
58 schema:name Corruption and Recovery-Efficient Locally Decodable Codes
59 schema:pagination 584-595
60 schema:productId N7b7e1ee35305418aa058f1236520ddbd
61 Ned95c183fe66454081e90306007860b3
62 schema:publisher N296216fbb2f748e2bd4939164530abbf
63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016904024
64 https://doi.org/10.1007/978-3-540-85363-3_46
65 schema:sdDatePublished 2022-12-01T06:49
67 schema:sdPublisher N8369631f6bcb4612b3885a05c4ddf5f2
68 schema:url https://doi.org/10.1007/978-3-540-85363-3_46
70 sgo:sdDataset chapters
71 rdf:type schema:Chapter
72 N1bd06d5198ea432b8a2455b559a854dd rdf:first sg:person.012727410605.86
73 rdf:rest rdf:nil
74 N296216fbb2f748e2bd4939164530abbf schema:name Springer Nature
75 rdf:type schema:Organisation
76 N3cf62aa4a59f4143bba0b71d737b8d3e rdf:first Nd5cc0af61a85436ebc17427b860b182b
77 rdf:rest N95d8efecc5864528b63b26a4768117bc
78 N6a6ffa3d8ab2455eb2eed27ae00c5633 schema:familyName Jansen
79 schema:givenName Klaus
80 rdf:type schema:Person
81 N7b7e1ee35305418aa058f1236520ddbd schema:name dimensions_id
82 schema:value pub.1016904024
83 rdf:type schema:PropertyValue
84 N7f96a4a82cfa438795a3925ee1cee7a8 rdf:first N6a6ffa3d8ab2455eb2eed27ae00c5633
85 rdf:rest N3cf62aa4a59f4143bba0b71d737b8d3e
86 N8369631f6bcb4612b3885a05c4ddf5f2 schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 N95d8efecc5864528b63b26a4768117bc rdf:first Ndb220ab2977841cab87d1775c42fd205
89 rdf:rest rdf:nil
90 Nbf166d957e774ae0ac663f35a786692a rdf:first Nfbea8cbc734f48f9af307f02743cff40
91 rdf:rest N7f96a4a82cfa438795a3925ee1cee7a8
92 Ncf2b6193558c479fa52149a6141a0468 schema:isbn 978-3-540-85362-6
93 978-3-540-85363-3
94 schema:name Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
95 rdf:type schema:Book
96 Nd5cc0af61a85436ebc17427b860b182b schema:familyName Rolim
97 schema:givenName José D. P.
98 rdf:type schema:Person
99 Ndb220ab2977841cab87d1775c42fd205 schema:familyName Rubinfeld
100 schema:givenName Ronitt
101 rdf:type schema:Person
102 Ned95c183fe66454081e90306007860b3 schema:name doi
103 schema:value 10.1007/978-3-540-85363-3_46
104 rdf:type schema:PropertyValue
105 Nfbea8cbc734f48f9af307f02743cff40 schema:familyName Goel
106 schema:givenName Ashish
107 rdf:type schema:Person
108 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
109 schema:name Medical and Health Sciences
110 rdf:type schema:DefinedTerm
111 anzsrc-for:1103 schema:inDefinedTermSet anzsrc-for:
112 schema:name Clinical Sciences
113 rdf:type schema:DefinedTerm
114 sg:person.012727410605.86 schema:affiliation grid-institutes:None
115 schema:familyName Woodruff
116 schema:givenName David
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86
118 rdf:type schema:Person