文章基本信息
- 标题：High-Entropy Dual Functions and Locally Decodable Codes (Extended Abstract)
- 本地全文：下载
- 作者：Justin Holmgren ; Farrokh Labib
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2021
- 卷号：185
- 页码：76:1-76:2
- DOI：10.4230/LIPIcs.ITCS.2021.76
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：Locally decodable codes (LDCs) allow any single encoded message symbol to be retrieved from a codeword with good probability by reading only a tiny number of codeword symbols, even if the codeword is partially corrupted. LDCs have surprisingly many applications in computer science and mathematics (we refer to [Yekhanin, 2012; Lovett, 2007] for extensive surveys). But despite their ubiquity, they are poorly understood. Of particular interest is the tradeoff between the codeword length N as a function of message length k when the query complexity - the number of probed codeword symbols - and alphabet size are constant. The Hadamard code is a 2-query LDC of length N = 2^O(k) and this length is optimal in the 2-query regime [Lovett, 2007]. For q ⥠3, near-exponential gaps persist between the best-known upper and lower bounds. The family of Reed-Muller codes, which generalize the Hadamard code, were for a long time the best-known examples, giving q-query LDCs of length exp(O(k^{1/(q-1)})), until breakthrough constructions of matching vector LDCs of Yekhanin and Efremenko [Yekhanin, 2008; Efremenko, 2012]. In contrast with other combinatorial objects such as expander graphs, the probabilistic method has so far not been successfully used to beat the best explicit LDC constructions. In [Lovett, 2007], a probabilistic framework was given that could in principle yield best-possible LDCs, albeit non-constructively. A special instance of this framework connects LDCs with a probabilistic version of Szemerédiâs theorem. The setup for this is as follows: For a finite abelian group G of size N = G , let D âS G be a random subset where each element is present with probability Ï independently of all others. For k ⥠3 and ε â^^ (0,1), let E be the event that every subset A âS G of size A ⥠ε G contains a proper k-term arithmetic progression with common difference in D. For fixed ε > 0 and sufficiently large N, it is an open problem to determine the smallest value of Ï - denoted Ï_k - such that Pr[E] ⥠1/2. In [Lovett, 2007] it is shown that there exist k-query LDCs of message length Ω(Ï_k N) and codeword length O(N). As such, Szemerédiâs theorem with random differences, in particular lower bounds on Ï_k, can be used to show the existence of LDCs. Conversely, this connection indirectly implies the best-known upper bounds on Ï_k for all k ⥠3 [Lovett, 2007; Lovett, 2007]. However, a conjecture from [Lovett, 2007] states that over â"¤_N we have Ï_k ⤠O_k(N^{-1}log N) for all k, which would be best-possible. Truth of this conjecture would imply that over this group, Szemerédiâs theorem with random differences cannot give LDCs better than the Hadamard code. For finite fields, Altman [Lovett, 2007] showed that this is false. In particular, over ð"½_pâ¿ for p odd, he proved that Ïâ,f ⥠Ω(p^{-n} n²); generally, Ï_k ⥠Ω(p^{-n} n^{k-1}) holds when p ⥠k 1 [Lovett, 2007]. In turn, these bounds are conjectured to be optimal for the finite-field setting, which would imply that over finite fields, Szemerédiâs theorem with random differences cannot give LDCs better than Reed-Muller codes. The finite-field conjecture is motivated mainly by the possibility that so-called dual functions can be approximated well by polynomial phases, functions of the form e^{2Ï i P(x)/p} where P is a multivariate polynomial over ð"½_p. We show that this is false. Using Yekhaninâs matching-vector-code construction, we give dual functions of order k over ð"½_pâ¿ that cannot be approximated in L_â^Z-distance by polynomial phases of degree k-1. This answers in the negative a natural finite-field analog of a problem of Frantzikinakis over â". [Lovett, 2007].
- 关键词：Higher-order Fourier analysis; dual functions; finite fields; additive combinatorics; coding theory
