Briët, Jop ;
Labib, Farrokh
HighEntropy Dual Functions and Locally Decodable Codes (Extended Abstract)
Abstract
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 2query LDC of length N = 2^O(k) and this length is optimal in the 2query regime [Lovett, 2007]. For q ≥ 3, nearexponential gaps persist between the bestknown upper and lower bounds. The family of ReedMuller codes, which generalize the Hadamard code, were for a long time the bestknown examples, giving qquery LDCs of length exp(O(k^{1/(q1)})), 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 bestpossible LDCs, albeit nonconstructively. 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 ⊆ 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 ⊆ G of size A ≥ ε G contains a proper kterm 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 kquery 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 bestknown 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 bestpossible. 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 ρ₃ ≥ Ω(p^{n} n²); generally, ρ_k ≥ Ω(p^{n} n^{k1}) holds when p ≥ k+1 [Lovett, 2007]. In turn, these bounds are conjectured to be optimal for the finitefield setting, which would imply that over finite fields, Szemerédi’s theorem with random differences cannot give LDCs better than ReedMuller codes.
The finitefield conjecture is motivated mainly by the possibility that socalled 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 matchingvectorcode construction, we give dual functions of order k over 𝔽_pⁿ that cannot be approximated in L_∞distance by polynomial phases of degree k1. This answers in the negative a natural finitefield analog of a problem of Frantzikinakis over ℕ [Lovett, 2007].
BibTeX  Entry
@InProceedings{briet_et_al:LIPIcs.ITCS.2021.76,
author = {Jop Bri\"{e}t and Farrokh Labib},
title = {{HighEntropy Dual Functions and Locally Decodable Codes}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {76:176:2},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13615},
URN = {urn:nbn:de:0030drops136157},
doi = {10.4230/LIPIcs.ITCS.2021.76},
annote = {Keywords: Higherorder Fourier analysis, dual functions, finite fields, additive combinatorics, coding theory}
}
04.02.2021
Keywords: 

Higherorder Fourier analysis, dual functions, finite fields, additive combinatorics, coding theory 
Seminar: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Issue date: 

2021 
Date of publication: 

04.02.2021 