Combinatorial lower bounds for 3-query LDCs
Combinatorial lower bounds for 3-query LDCs
复制标题
3 查询 LDC 的组合下限
DOI：
10.4230/lipics.itcs.2020.85
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Suprovat Ghoshal
中科院分区：
文献类型：
--
作者：
Arnab Bhattacharyya;L. Chandran;Suprovat Ghoshal
如果存在一种随机解码算法，对于给定的索引\(i\)以及一个与消息\(x\)的编码相近的接收字\(w\)，通过对\(w\)最多查询\(q\)个坐标就能输出\(x_i\)，那么这样的编码被称为\(q\) - 查询局部可解码编码（LDC）。理解LDC的维度、长度和查询复杂度之间的权衡是一个极具吸引力且尚未解决的研究挑战。特别是，对于维度为\(k\)且长度为\(n\)的\(3\) - 查询二进制LDC，目前已知的最佳界限是：\(2^{k^{o(1)}} \geq n \geq \tilde{\Omega}(k^2)\)。
在这项工作中，我们重新审视二进制\(3\) - 查询LDC。我们研究了一类与强二进制\(3\) - 查询LDC等价的\(3\) - 均匀超图。我们证明了这些超图中边的数量的一个上界，重现了强\(3\) - 查询LDC长度的已知下界\(\tilde{\Omega}(k^2)\)。与先前的工作不同，我们的技术是纯组合的，不依赖于直接归约到\(2\) - 查询LDC，这为分析\(3\) - 查询LDC开辟了一种可能不同的方法。
A code is called a $q$-query locally decodable code (LDC) if there is a randomized decoding algorithm that, given an index $i$ and a received word $w$ close to an encoding of a message $x$, outputs $x_i$ by querying only at most $q$ coordinates of $w$. Understanding the tradeoffs between the dimension, length and query complexity of LDCs is a fascinating and unresolved research challenge. In particular, for $3$-query binary LDCs of dimension $k$ and length $n$, the best known bounds are: $2^{k^{o(1)}} \geq n \geq \tilde{\Omega}(k^2)$.
In this work, we take a second look at binary $3$-query LDCs. We investigate a class of 3-uniform hypergraphs that are equivalent to strong binary 3-query LDCs. We prove an upper bound on the number of edges in these hypergraphs, reproducing the known lower bound of $\tilde{\Omega}(k^2)$ for the length of strong $3$-query LDCs. In contrast to previous work, our techniques are purely combinatorial and do not rely on a direct reduction to $2$-query LDCs, opening up a potentially different approach to analyzing 3-query LDCs.