High-entropy dual functions over finite fields and locally decodable codes

Jop Briët, Farrokh Labib

We show that for infinitely many primes $p$, there exist dual functions of order $k$ over ${\mathbb{F}}_p^n$ that cannot be approximated in $L_{\infty }$-distance by polynomial phase fu…