2021-01-06
High-entropy dual functions over finite fields and locally decodable codes
Publication
Publication
Presented at the
12th Innovations in Theoretical Computer Science Conference (ITCS 2021) (January 2021), Online
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.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.4230/LIPIcs.ITCS.2021.76 | |
| Leibniz International Proceedings in Informatics (LIPIcs) | |
| 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) | |
| Organisation | Algorithms and Complexity |
|
Briët, J., & Labib, F. (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 |
|
