# A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field

Ontology type: schema:ScholarlyArticle

### Article Info

DATE

2012-07-12

AUTHORS ABSTRACT

A linear (q, δ, ϵ,m(n))-locally decodable code (LDC) C : \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb F}$\end{document}n→\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb F}$\end{document}m(n) is a linear transformation from the vector space \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb F}$\end{document}n to the space \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb F}$\end{document}m(n) for which each message symbol xi 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}{{\left| \mathbb{F} \right|}} + \varepsilon$\end{document} from C(x) by a randomized algorithm that queries only q positions of C(x), even if up to δm(n) positions of C(x) are corrupted. In a recent work of Dvir, the author shows that lower bounds for linear LDCs can imply lower bounds for arithmetic circuits. He suggests that proving lower bounds for LDCs over the complex or real field is a good starting point for approaching one of his conjectures. Our main result is an m(n) = Ω(n2) lower bound for linear 3-query LDCs over any, possibly infinite, field. The constant in the Ω(·) depends only on ε and δ. This is the first lower bound better than the trivial m(n) = Ω(n) for arbitrary fields and more than two queries. More... »

PAGES

678-686

### References to SciGraph publications

• 2010. Locally Decodable Codes and Private Information Retrieval Schemes in NONE
• 1977. Graph-theoretic arguments in low-level complexity in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1977
• 2008-01-01. Corruption and Recovery-Efficient Locally Decodable Codes in APPROXIMATION, RANDOMIZATION AND COMBINATORIAL OPTIMIZATION. ALGORITHMS AND TECHNIQUES
• 1984. Sequences and Series in Banach Spaces in NONE
• 2010. Graph Theory in NONE
• 2002-08-23. Optimal Lower Bounds for 2-Query Locally Decodable Linear Codes in RANDOMIZATION AND APPROXIMATION TECHNIQUES IN COMPUTER SCIENCE

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s11390-012-1254-8

DOI

http://dx.doi.org/10.1007/s11390-012-1254-8

DIMENSIONS

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

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/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "IBM Almaden Research Center, 10598, Yorktown Heights, N.Y., U.S.A",
"id": "http://www.grid.ac/institutes/None",
"name": [
"IBM Almaden Research Center, 10598, Yorktown Heights, N.Y., U.S.A"
],
"type": "Organization"
},
"familyName": "Woodruff",
"givenName": "David P.",
"id": "sg:person.012727410605.86",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/978-3-540-85363-3_46",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1016904024",
"https://doi.org/10.1007/978-3-540-85363-3_46"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4612-5200-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1034000175",
"https://doi.org/10.1007/978-1-4612-5200-9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-14358-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015165842",
"https://doi.org/10.1007/978-3-642-14358-8"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-45726-7_4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013133273",
"https://doi.org/10.1007/3-540-45726-7_4"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-14279-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1109709680",
"https://doi.org/10.1007/978-3-642-14279-6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-08353-7_135",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1025032395",
"https://doi.org/10.1007/3-540-08353-7_135"
],
"type": "CreativeWork"
}
],
"datePublished": "2012-07-12",
"datePublishedReg": "2012-07-12",
"description": "A linear (q, \u03b4, \u03f5,m(n))-locally decodable code (LDC) C : \\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}$\\end{document}n\u2192\\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}$\\end{document}m(n) is a linear transformation from the vector space \\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}$\\end{document}n to the space \\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}$\\end{document}m(n) for which each message symbol xi 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}{{\\left| \\mathbb{F} \\right|}} + \\varepsilon$\\end{document} from C(x) by a randomized algorithm that queries only q positions of C(x), even if up to \u03b4m(n) positions of C(x) are corrupted. In a recent work of Dvir, the author shows that lower bounds for linear LDCs can imply lower bounds for arithmetic circuits. He suggests that proving lower bounds for LDCs over the complex or real field is a good starting point for approaching one of his conjectures. Our main result is an m(n)\u2009=\u2009\u03a9(n2) lower bound for linear 3-query LDCs over any, possibly infinite, field. The constant in the \u03a9(\u00b7) depends only on \u03b5 and \u03b4. This is the first lower bound better than the trivial m(n)\u2009=\u2009\u03a9(n) for arbitrary fields and more than two queries.",
"genre": "article",
"id": "sg:pub.10.1007/s11390-012-1254-8",
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1357568",
"issn": [
"1000-9000",
"1860-4749"
],
"name": "Journal of Computer Science and Technology",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "4",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"lower bounds",
"starting point",
"recent work",
"space",
"good starting point",
"linear transformation",
"vector space",
"randomized algorithm",
"authors",
"arbitrary field",
"code C",
"position",
"work",
"bounds",
"real field",
"field",
"linear",
"transformation",
"Q positions",
"main results",
"decodable codes",
"XI",
"linear LDCs",
"conjecture",
"queries",
"probability",
"algorithm",
"arithmetic circuits",
"point",
"code",
"Dvir",
"LDCs",
"circuit",
"results"
],
"name": "A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field",
"pagination": "678-686",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1004236284"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s11390-012-1254-8"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s11390-012-1254-8",
"https://app.dimensions.ai/details/publication/pub.1004236284"
],
"sdDataset": "articles",
"sdDatePublished": "2022-11-24T20:56",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_556.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s11390-012-1254-8"
}
]

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/s11390-012-1254-8'

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/s11390-012-1254-8'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11390-012-1254-8'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11390-012-1254-8'

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

111 TRIPLES      21 PREDICATES      63 URIs      50 LITERALS      6 BLANK NODES

Subject Predicate Object
2 schema:author N85bcf123d3a44004b52d865384a95911
3 schema:citation sg:pub.10.1007/3-540-08353-7_135
4 sg:pub.10.1007/3-540-45726-7_4
5 sg:pub.10.1007/978-1-4612-5200-9
6 sg:pub.10.1007/978-3-540-85363-3_46
7 sg:pub.10.1007/978-3-642-14279-6
8 sg:pub.10.1007/978-3-642-14358-8
9 schema:datePublished 2012-07-12
10 schema:datePublishedReg 2012-07-12
11 schema:description A linear (q, δ, ϵ,m(n))-locally decodable code (LDC) C : \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb F}$\end{document}n→\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb F}$\end{document}m(n) is a linear transformation from the vector space \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb F}$\end{document}n to the space \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb F}$\end{document}m(n) for which each message symbol xi 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}{{\left| \mathbb{F} \right|}} + \varepsilon$\end{document} from C(x) by a randomized algorithm that queries only q positions of C(x), even if up to δm(n) positions of C(x) are corrupted. In a recent work of Dvir, the author shows that lower bounds for linear LDCs can imply lower bounds for arithmetic circuits. He suggests that proving lower bounds for LDCs over the complex or real field is a good starting point for approaching one of his conjectures. Our main result is an m(n) = Ω(n2) lower bound for linear 3-query LDCs over any, possibly infinite, field. The constant in the Ω(·) depends only on ε and δ. This is the first lower bound better than the trivial m(n) = Ω(n) for arbitrary fields and more than two queries.
12 schema:genre article
13 schema:isAccessibleForFree false
14 schema:isPartOf N5675a00b11544ee9a9e00c67da810639
15 Nc6f3aec7cc6b475da382a79218060c7f
16 sg:journal.1357568
17 schema:keywords Dvir
18 LDCs
19 Q positions
20 XI
21 algorithm
22 arbitrary field
23 arithmetic circuits
24 authors
25 bounds
26 circuit
27 code
28 code C
29 conjecture
30 decodable codes
31 field
32 good starting point
33 linear
34 linear LDCs
35 linear transformation
36 lower bounds
37 main results
38 point
39 position
40 probability
41 queries
42 randomized algorithm
43 real field
44 recent work
45 results
46 space
47 starting point
48 transformation
49 vector space
50 work
51 schema:name A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field
52 schema:pagination 678-686
53 schema:productId N2336a4d93bb542fea64b1d7fbb2068e1
54 N8a3491cd793d4f0cbbd2e53dd81e11e0
55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004236284
56 https://doi.org/10.1007/s11390-012-1254-8
57 schema:sdDatePublished 2022-11-24T20:56
59 schema:sdPublisher N0874dfede10d416e85abf954e2570334
60 schema:url https://doi.org/10.1007/s11390-012-1254-8
62 sgo:sdDataset articles
63 rdf:type schema:ScholarlyArticle
64 N0874dfede10d416e85abf954e2570334 schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 N2336a4d93bb542fea64b1d7fbb2068e1 schema:name dimensions_id
67 schema:value pub.1004236284
68 rdf:type schema:PropertyValue
69 N5675a00b11544ee9a9e00c67da810639 schema:issueNumber 4
70 rdf:type schema:PublicationIssue
71 N85bcf123d3a44004b52d865384a95911 rdf:first sg:person.012727410605.86
72 rdf:rest rdf:nil
73 N8a3491cd793d4f0cbbd2e53dd81e11e0 schema:name doi
74 schema:value 10.1007/s11390-012-1254-8
75 rdf:type schema:PropertyValue
77 rdf:type schema:PublicationVolume
78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
79 schema:name Information and Computing Sciences
80 rdf:type schema:DefinedTerm
81 sg:journal.1357568 schema:issn 1000-9000
82 1860-4749
83 schema:name Journal of Computer Science and Technology
84 schema:publisher Springer Nature
85 rdf:type schema:Periodical
86 sg:person.012727410605.86 schema:affiliation grid-institutes:None
87 schema:familyName Woodruff
88 schema:givenName David P.
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86
90 rdf:type schema:Person
91 sg:pub.10.1007/3-540-08353-7_135 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025032395
92 https://doi.org/10.1007/3-540-08353-7_135
93 rdf:type schema:CreativeWork
94 sg:pub.10.1007/3-540-45726-7_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013133273
95 https://doi.org/10.1007/3-540-45726-7_4
96 rdf:type schema:CreativeWork
97 sg:pub.10.1007/978-1-4612-5200-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034000175
98 https://doi.org/10.1007/978-1-4612-5200-9
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/978-3-540-85363-3_46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016904024
101 https://doi.org/10.1007/978-3-540-85363-3_46
102 rdf:type schema:CreativeWork
103 sg:pub.10.1007/978-3-642-14279-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109709680
104 https://doi.org/10.1007/978-3-642-14279-6
105 rdf:type schema:CreativeWork
106 sg:pub.10.1007/978-3-642-14358-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015165842
107 https://doi.org/10.1007/978-3-642-14358-8
108 rdf:type schema:CreativeWork
109 grid-institutes:None schema:alternateName IBM Almaden Research Center, 10598, Yorktown Heights, N.Y., U.S.A
110 schema:name IBM Almaden Research Center, 10598, Yorktown Heights, N.Y., U.S.A
111 rdf:type schema:Organization