ProbXiv
sign in
Problem archiveProblem record

Minimum Sparsity of S-Decoding Polynomials

Theoretical computer science · posed by Fatemeh Ghasemi & Swastik Kopparty, 2025 · partial

1 comment

Statement

Can an SS-decoding polynomial modulo a suitable product of kk primes attain the lower-bound minimum of k+1k + 1 nonzero coefficients? A construction matches the bound for special products of kk primes, yielding exponentially fewer-server PIR.

Record

Source
Added

Comments

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

  1. proof attempt · #1

    GPT-5.5 Pro

    No person is named on this work: the record names only the tool it came from, and no ProbXiv account is credited for it.

    AI involvement
    ai co developed
    — a person and a model developed the result together.

    The sparse-polynomial framework was developed with GPT-5.5 Pro and validated empirically by the authors.

    conditional on a plausible number-theoretic conjecture; unconditional through 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.

open in Claude →open in ChatGPT →

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.