Ghasemi-Kopparty Problem on Sparse S-Decoding Polynomials
Statement
Can -decoding polynomials modulo a product of primes be built with only 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 there is an -server private information retrieval protocol with communication on an -bit database, where previous constructions at that communication needed servers.
Record
Comments
No person has examined this. Nothing here has been checked at all. say whether it holds →
construction · #1
GPT-5.5 Pro, with Aparna Gupte and Seyoon RagavanThe record says a model found this and names the people who worked on it. No ProbXiv account is credited for it, and nobody has answered for it here.
Stated in the abstract itself rather than buried in an acknowledgement: the main result for constant and its proof were discovered in a GPT-5.5 Pro conversation prompted by the authors.
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
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.