Ghasemi-Kopparty Problem on Sparse $S$ -Decoding Polynomials

Can $S$ -decoding polynomials modulo a product of $k$ primes be built with only $k+1$ nonzero coefficients, the minimum their own lower bound allows? Yes, via a general framework for special prime products. The consequence is that for any constant $s$ there is an $s$ -server private information retrieval protocol with communication $\exp(O((\log n)^{1/s}(\log\log n)^{1-1/s}))$ on an $n$ -bit database, where previous constructions at that communication needed $2^{O(s)}$ servers.

Result: Proved(see note)
Status: Resolved
AI contribution: AI-discovered
Method: Construction
Field: Computational complexity
Posed by: Mahdi Ghasemi, Swastik Kopparty
Year posed: 2026
Years open: 0y
Solved: 2026-07-24
Model: GPT-5.5 Pro
Vendor: OpenAI
Collaborators: Aparna Gupte, Seyoon Ragavan
Verification: Unreviewed
Publication: Preprint
Significance: 15 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

the PIR consequence is conditional on a number-theoretic conjecture implied by either the generalized repunit conjecture or Schinzel's hypothesis H, and is unconditional for s <= 15

What the AI did

Stated in the abstract itself rather than buried in an acknowledgement: the main result for constant $s$ and its proof were discovered in a GPT-5.5 Pro conversation prompted by the authors.

Verification

arXiv preprint; the authors also empirically validate the construction and make the result unconditional for all $s \le 15$ . Not yet peer-reviewed.

Source

arXiv:2607.22033 - Exponentially Fewer-Server PIR from Sparser S-Decoding Polynomials

Ghasemi-Kopparty Problem on Sparse SSS-Decoding Polynomials

What was actually shown

What the AI did

Verification

Source

Discussion

Ghasemi-Kopparty Problem on Sparse $S$ -Decoding Polynomials