Minimum Sparsity of S-Decoding Polynomials
Can an -decoding polynomial modulo a suitable product of primes attain the lower-bound minimum of nonzero coefficients? A construction matches the bound for special products of primes, yielding exponentially fewer-server PIR.
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI co-developed
- Method
- Argument
- Field
- Private information retrieval
- Posed by
- Fatemeh Ghasemi & Swastik Kopparty
- Year posed
- 2025
- Years open
- 1y
- Solved
- 2026-07-24
- Model
- GPT-5.5 Pro
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 5 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
conditional on a plausible number-theoretic conjecture; unconditional through s = 15
What the AI did
The sparse-polynomial framework was developed with GPT-5.5 Pro and validated empirically by the authors.
Verification
Author-checked ePrint with empirical validation of the construction. Not yet peer-reviewed.
Source
ePrint 2026/1515 - Exponentially fewer-server PIR from sparser S-decoding polynomials