Exponentially Fewer-Server PIR from Sparser $S$-Decoding Polynomials

• URL: http://arxiv.org/abs/2607.22033v1
• Date: Fri, 24 Jul 2026 06:59:30 GMT
• Title: Exponentially Fewer-Server PIR from Sparser $S$-Decoding Polynomials
• Abstract summary: We show that for any constant $s$ there exists an $s$-server private information retrieval protocol.<n>Our number-theoretic conjecture is implied by existing conjectures.
• Score: 2.5782420501870296
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show that under a plausible number-theoretic conjecture, for any constant $s$ there exists an $s$-server private information retrieval (PIR) protocol that on an $n$-bit database requires communication $\exp(O((\log n)^{1/s} (\log \log n)^{1-1/s}))$. Previous constructions attaining the same communication required $2^{O(s)}$ servers. Our number-theoretic conjecture is implied by existing conjectures, namely the generalized repunit conjecture and Schinzel's hypothesis H (either one of these conjectures would suffice alone). Our result builds on the ``matching vector family + $S$-decoding polynomials'' framework pioneered by Efremenko (STOC 2009) and recently refined by Ghasemi, Kopparty, and Sudan (STOC 2025). The main ingredient is a framework for constructing $S$-decoding polynomials with only $k+1$ nonzero coefficients modulo special products of $k$ primes, resolving an open problem posed by Ghasemi and Kopparty (ITCS 2026). By the lower bound shown by Ghasemi and Kopparty, this is the minimum achievable sparsity. We also empirically validate our construction and make our result unconditional for all $s \leq 15$. We also apply our techniques to regimes where $s$ grows with $n$, showing under a stronger variant of our number-theoretic conjecture that the communication complexity of $s$-server matching-vector PIR can be superpolynomially reduced from the previous state of the art for any $s \leq \exp(o(\sqrt{\log \log n/\log \log \log n}))$. The main result for $s = O(1)$ and its proof were discovered in a GPT-5.5 Pro conversation prompted by the authors.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$ can affect prediction by scale $r_j$ and enters only $n_T,j=T-j+1$ prediction rounds.<n>For every summable envelope, a localized mixture proves $cR_T(r)leq C_T(r)$.<n>For exponential and envelopes, under the stated finite-sample condition, a Toeplitz-design converse proves $cR_T(r)geq c_T(r)$.
  arXiv  Detail & Related papers  (2026-08-27T01:31:46Z)
• Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening [26.60272178029048]
  We show a protocol achieving utility at least $- using only $2mathcal O(CC_(G))/2$ bits of communication.<n>We note that our results strictly weaken the assumptions required by prior work in the multi-agent information aggregation literature.
  arXiv  Detail & Related papers  (2026-08-05T18:34:19Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  We present two quantum algorithms that produce the normalized solution $|xrangle$ of linear system $Ax=| b rangle$ to accuracy $$ with complexity independent of the condition number $=lVert A-1rVert$.<n>Our filtering-based solver is extremely simple with a favorable runtime prefactor.
  arXiv  Detail & Related papers  (2026-07-08T17:49:40Z)
• Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE [0.0]
  The PRIM-LWE problem is a variant of the Learning with Errors problem in which the secret matrix is required to have a primitive-root determinant.<n>We show that the limiting distribution of $c(p)$ over the primes has support exactly $[0,1/2]$.<n>We also derive explicit lower bounds on $c(q)$ for primes of cryptographic interest, parameterized solely by the number of distinct prime factors of $q-1$.
  arXiv  Detail & Related papers  (2026-03-11T18:04:48Z)
• Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits [5.130304470169084]
  We show that the existence of demi-bits generators implies $textAvoid$ is hard for nondeterministic algorithms.<n>We transform demi-bits generators to proof complexity generators that are *pseudo-surjective* with nearly optimal parameters.
  arXiv  Detail & Related papers  (2025-11-18T02:40:39Z)
• Efficiently Batching Unambiguous Interactive Proofs [8.993111413196559]
  We show that if a language $L$ admits a publiccoin interactive proof (UIP) with round $ell$, where $a$ bits are communicated per round, then the batch language $Lotimes k$, i.e. the set of $k$-tuples of statements all belonging to $Lotimes k$, has unambiguous interactive proof with complexity $ellcdotmathsfpolylog(k)$, per-round communication of $acdot ellcdotmathsfpolylog(k
  arXiv  Detail & Related papers  (2025-10-21T21:04:10Z)
• PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
  We introduce $mathsfPREM$ (Private Relative Error Multiplicative weight update), a new framework for generating synthetic data that a relative error guarantee for statistical queries under $(varepsilon, delta)$ differential privacy (DP)<n>We complement our algorithm with nearly matching lower bounds.
  arXiv  Detail & Related papers  (2025-02-20T18:32:02Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.