文章基本信息

标题：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