High-entropy dual functions over finite fields and locally decodable codes
We show that for infinitely many primes p, there exist dual functions of order k over Fnp that cannot be approximated in L∞-distance by polynomial phase functions of degree k−1. This answers in the negative a natural finite-field analog of a problem of Frantzikinakis on L∞-approximations of dual functions over N (a.k.a. multiple correlation sequences) by nilsequences.
|, , , ,|
|Leibniz International Proceedings in Informatics|
|12th Innovations in Theoretical Computer Science Conference (ITCS 2021)|
|Organisation||Algorithms and Complexity|
Briët, J, & Labib, F.S. (2021). High-entropy dual functions over finite fields and locally decodable codes. In Innovations in Theoretical Computer Science Conference. doi:10.4230/LIPIcs.ITCS.2021.76