High-entropy dual functions and locally decodable codes
summary
Shows a negative result: for infinitely many primes P there exists a K(P) and explicit families of order-k dual functions over F_p^n that cannot be approximated in L_infty by polynomial phases of degree ≤ K−1. Proof builds on the matching vector construction (Mersenne-prime case) to produce ≳ N^T orthogonal pairs and a high-dimensional hypercube of size ≥ N^T inside the dual functions, then counts polynomial phases (≤ p^{N^{K−1}}) and applies geometric functional analysis to rule out uniform approximation. This disproves the finite-field approximation conjecture.
AI-written summary · about
chapters (8)
- 0:00Start
- 0:41Locally decodable codes
- 4:50Constructing LDCs using the probabilistic method
- 6:02Szemerédi's theorem with random differences (1/3)
- 15:53Arithmetic progression dual functions
- 17:25General dual functions
- 18:08Decompositions of dual functions (2/2)
- 32:48Open problems
related talks
46mCodes with the multiplication property
01h 04mHow to Encrypt a Functionality
51mWhat Can and What Cannot Be Done by LP and SDP (An Incomplete Overview)
46mList-decoding random codes ensembles
58mObfuscation 2
53mThe Hermitian Trace Code
01h 09mWhen Cryptography Meets Modern Channel Coding
01h 07mComputing on Encrypted Data via Secret Dual Codes