Sparsity of decoding polynomials and fixed-server PIR
Follow the latest progress by email.
Can an S*_m-decoding polynomial associated with a k-prime modulus have only k+1 nonzero terms, matching the known sparsity lower bound? The general construction is conditional on the cited large-prime-divisor Conjecture 1.1.
Why it matters and what counts as progress
Why it matters: Optimal sparsity improves the associated fixed-server private-information-retrieval trade-off.
What counts as progress: A k+1-term construction under explicit prime and finite-field conditions, an unconditional extension beyond the checked server range, or a stronger sparsity obstruction.
How the problem developed
- 31 May 2009 · Construction [1]
Klim Efremenko Introduced unconditional subexponential-length constant-query locally decodable codes using matching-vector methods, a foundation for later matching-vector PIR work.
- December 2025 · Lower bound and question [2]
Fatemeh Ghasemi and Swastik Kopparty Studied Fourier sparsity of delta functions and S-decoding polynomials, proved an r+1 monomial lower bound for the canonical set, and identified sparse decoding polynomials as a route to improving matching-vector PIR.
- 16 Oct 2026 · Construction [3]
Aparna Gupte and Seyoon Ragavan Reported k+1-sparse S-decoding polynomials under a number-theoretic conjecture, matching the lower bound and improving fixed-server PIR; the paper states an unconditional result for s≤15.
AI contribution
Exponentially Fewer-Server PIR from Sparser S-Decoding Polynomials
Conditional on Conjecture 1.1 about large prime divisors, the authors construct an S*_m-decoding polynomial with the optimal k+1 nonzero terms for every fixed k, for suitable k-prime m and finite field. The construction gives the stated fixed-server PIR tradeoff; finite prime checks make it unconditional through 15 servers.
Sources
Website timeline
Publication dates and editorial changes.