We use cookies to improve your experience with our site.

一种任意域上3查询线性可局部解码编码的二次下限

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

  • 摘要: 线性的(q,δ,?,m(n))-可局部解码编码(LDC)C:Fn→Fm(n)是一种从向量空间Fn到向量空间Fm(n)的线性转换,使得每个消息符号可以以至少1/(|F|)+∈的概率通过一种随机算法,只检索C(x)的q个位置,即便C(x)中的δm(n)个位置被破坏,也能从C(x)得到恢复。在Dvir的一项最近工作中,作者提出线性LDC的下限能推导出算术单元电路的下限。他提出证明复(实)数域上的LDC的下限是得到他的猜测的很好的起点。我们的主要结果是线性3-query LDC在任何(可能无穷)域上的下限。Ω(·)上的常量仅依赖?和δ。这是第一个针对任意域和大于两个查询的、比平凡m(n)=Ω(n)更好的下限。

     

    Abstract: A linear (q, δ, ?, m(n))-locally decodable code (LDC) C:Fn→Fm(n) is a linear transformation from the vector space Fn to the space Fm(n) for which each message symbol xi can be recovered with probability at least 1/|F| + ? 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.

     

/

返回文章
返回