論文の概要: Exponentially Fewer-Server PIR from Sparser $S$-Decoding Polynomials
- arxiv url: http://arxiv.org/abs/2607.22033v1
- Date: Fri, 24 Jul 2026 06:59:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-27 20:58:57.06863
- Title: Exponentially Fewer-Server PIR from Sparser $S$-Decoding Polynomials
- Title（参考訳）: Sparser $S$-decode Polynomials の指数的に少ないPIR
- Abstract要約: 一定の$s$に対して、$s$サーバのプライベート情報検索プロトコルが存在することを示す。
我々の数論予想は既存の予想によって示唆される。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 任意の定数$s$に対して、$n$-bitデータベース上に$\exp(O((\log n)^{1/s} (\log \log n)^{1-1/s})$という通信を必要とする$s$サーバプライベート情報検索(PIR)プロトコルが存在することを示す。
以前の同じ通信を実現するには、$2^{O(s)} のサーバが必要だった。
我々の数論的な予想は、既存の予想、すなわち一般化されたreunit予想とシンツェルの仮説 H によって示唆される。
この結果は,Efremenko (STOC 2009) が先駆的であり,最近 Ghasemi, Kopparty, Sudan (STOC 2025) が改良した 'matching vector family + $S$-decoding polynomials' フレームワークに基づいている。
主な要素は、$k+1$の非ゼロ係数のみを持つ$S$復号多項式を構成するためのフレームワークであり、Ghasemi と Kopparty (ITCS 2026) によって引き起こされる開問題を解決している。
Ghasemi と Kopparty によって示される下界により、これは達成可能な最小の空間である。
また、我々の構成を実証的に検証し、その結果をすべての$s \leq 15$に対して無条件にする。
我々はまた、$s$が$n$で成長するレジームにも適用し、$s$-server matching-vector PIRの通信複雑性が、任意の$s \leq \exp(o(\sqrt{\log \log n/\log \log \log n})$に対して以前の状態から双項的に減少できるという我々の数論的予想のより強い変種の下で示している。
s = O(1)$ と証明の主な結果は、著者らによる GPT-5.5 Pro の会話で発見された。
関連論文リスト
- A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳（メタデータ） (2026-09-09T10:13:43Z) - Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。
すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。
指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
論文 参考訳（メタデータ） (2026-08-27T01:31:46Z) - Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening [26.60272178029048]
我々は,少なくとも$-を達成するためのプロトコルを,2$mathcal O(CC_(G))/2$の通信ビットのみを用いて示す。
本研究の結果は,マルチエージェント情報集約文学における先行研究で要求される仮定を厳格に弱めることに留意する。
論文 参考訳（メタデータ） (2026-08-05T18:34:19Z) - The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。
我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
論文 参考訳（メタデータ） (2026-08-03T17:57:01Z) - Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。
フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文 参考訳（メタデータ） (2026-07-08T17:49:40Z) - Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE [0.0]
PRIM-LWE問題はLearning with Errors問題の変種であり、秘密行列はプリミティブ・ルート行列式を持つ必要がある。
素数上の$c(p)$の極限分布は、正確に$[0,1/2]$であることを示す。
また、暗号的興味を持つ素数に対して$c(q)$の明示的な下限を導出し、q-1$の別個の素数だけによってパラメータ化する。
論文 参考訳（メタデータ） (2026-03-11T18:04:48Z) - Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits [5.130304470169084]
非決定論的アルゴリズムでは、demi-bits ジェネレータの存在は$textAvoid$ が難しいことを示す。
我々はデミビット生成器を *pseudo-surjective* でほぼ最適パラメータを持つ複雑性生成器の証明に変換する。
論文 参考訳（メタデータ） (2025-11-18T02:40:39Z) - Efficiently Batching Unambiguous Interactive Proofs [8.993111413196559]
例えば、$Lotimes k$に属するステートメントのセット$k$-tuplesは、複雑さを伴うあいまいなインタラクティブな証明を持つ。 $ellcdotmathsfpolylog(k)$、$acdot ellcdotmathsfpolylog(k)$、ラウンドごとの通信である。
論文 参考訳（メタデータ） (2025-10-21T21:04:10Z) - PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。
我々はアルゴリズムをほぼ一致する下界で補完する。
論文 参考訳（メタデータ） (2025-02-20T18:32:02Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。