文章基本信息
- 标题：Combinatorial Lower Bounds for 3-Query LDCs
- 本地全文：下载
- 作者：Arnab Bhattacharyya ; L. Sunil Chandran ; Suprovat Ghoshal 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：151
- 页码：1-8
- DOI：10.4230/LIPIcs.ITCS.2020.85
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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 LDCâs of dimension k and length n, the best known bounds are: 2^{k^o(1)} ⥠n ⥠Ω Ìf(k²). 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 Ω Ìf(k²) 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.
- 关键词：Coding theory; Graph theory; Hypergraphs
