ProbXiv
sign in
Problem archiveProblem record

Statement

Can SS-decoding polynomials modulo a product of kk primes be built with only k+1k+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 ss there is an ss-server private information retrieval protocol with communication exp⁡(O((log⁡n)1/s(log⁡log⁡n)1−1/s))\exp(O((\log n)^{1/s}(\log\log n)^{1-1/s})) on an nn-bit database, where previous constructions at that communication needed 2O(s)2^{O(s)} servers.

Record

Comments

No person has examined this. Nothing here has been checked at all. say whether it holds →

  1. construction · #1

    GPT-5.5 Pro, with Aparna Gupte and Seyoon Ragavan

    The 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.

    AI involvement
    ai discovered
    — the result was found by a model.

    Stated in the abstract itself rather than buried in an acknowledgement: the main result for constant ss 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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.