theoretical-computer-science / Computational complexity
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.
Temporal state
No reconciled state yet.
Append-only history
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
Research memory
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.
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
Evidence graph
No public relationships recorded yet.