A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2012-07-12

AUTHORS

David P. Woodruff

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: 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/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", 
            "volumeNumber": "27"
          }
        ], 
        "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", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "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"
      }
    ]
     

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

    Turtle is a human-readable linked data format.

    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
    1 sg:pub.10.1007/s11390-012-1254-8 schema:about anzsrc-for:08
    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
    58 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    59 schema:sdPublisher N0874dfede10d416e85abf954e2570334
    60 schema:url https://doi.org/10.1007/s11390-012-1254-8
    61 sgo:license sg:explorer/license/
    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
    76 Nc6f3aec7cc6b475da382a79218060c7f schema:volumeNumber 27
    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
     




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


    ...