論文の概要: Provably Subexponential Algorithms for Bounded-Error LWE with Few Samples

• arxiv url: http://arxiv.org/abs/2610.13043v1
• Date: Fri, 09 Oct 2026 05:58:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-13 04:06:29.41573
• Title: Provably Subexponential Algorithms for Bounded-Error LWE with Few Samples
• Title（参考訳）: 少数のサンプルを持つ有界誤差LWEの確率的部分指数アルゴリズム
• Abstract要約: 我々は、Kirchner and Fouque [KF15] の LWE に対する Wagner/BKW 型アルゴリズムの変種が決定を解き、LWE の秘密を素モジュライ$q=n+o(1)$で検索することを示した。
• 参考スコア（独自算出の注目度）: 3.845877724862319
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show that a variant of the Wagner/BKW-style algorithm for LWE of Kirchner and Fouque [KF15] solves decision and search LWE with secrets of size $n$ over prime moduli $q=n^{κ+o(1)}$, for any fixed $κ>0$, with errors bounded by $\exp((\ln n)^{o(1)})$, in time $2^{O(n/\ln\ln n)}$ given $n+O(n/\ln\ln n)$ original samples. Further, if each coordinate of the secret is also bounded by $\exp((\ln n)^{o(1)})$, the same time bound holds with errors bounded by $n^{o(1)}$ and only $O(n/\ln\ln q)$ samples. Earlier, it was known that Kirchner and Fouque's algorithm could solve LWE with these parameters in subexponential time with a much larger number of samples $m = Ω(n\log{n})$ [HKM18]. Ducas et al. [DEL25] showed that an adaptation of this algorithm could solve the corresponding dual, the $\mathrm{SIS}^{\infty}$ problem, with a suitable norm bound $q/\operatorname{polylog}(n)$ and $m=n+ω(n/\ln\ln n)$ variables in subexponential time. Whereas their analysis involves interpreting the algorithm in terms of chains of lattices, our approach is quite elementary and is based on bounding the lower moments of a Fourier statistic.
• Abstract（参考訳）: 我々は、Kirchner と Fouque [KF15] の LWE に対する Wagner/BKW スタイルのアルゴリズムの変種が決定を解き、LWE の秘密を$n$ over prime moduli $q=n^{κ+o(1)}$, for any fixed $κ>0$, with error bounded by $\exp((\ln n)^{o(1)})$, in time $2^{O(n/\ln\ln n)}$ given $n+O(n/\ln\lnnnn)$.} で探索することを示した。 さらに、秘密の座標が$\exp((\ln n)^{o(1)})$で有界であれば、同じ時間は$n^{o(1)}$と$O(n/\ln\ln q)$で有界な誤差を持つ。 以前、Kirchner と Fouque のアルゴリズムはこれらのパラメータをサブ指数時間で解くことができ、より多くのサンプルが $m = Ω(n\log{n})$ [HKM18] であることがわかった。 Ducas et al [DEL25] は、このアルゴリズムの適応が対応する双対である $\mathrm{SIS}^{\infty}$ を解くことができ、適当なノルムは$q/\operatorname{polylog}(n)$と$m=n+ω(n/\ln\lnn)$変数であることを示した。 彼らの分析では格子の連鎖の観点でアルゴリズムを解釈するが、我々のアプローチは非常に初等的であり、フーリエ統計学の下位モーメントの有界性に基づいている。

関連論文リスト

• Fast Quantum Algorithms for Learning Linear Threshold Functions [42.535091514980515]
  線形しきい値関数は$f_w,(x)=textsign(langle x,w rangle -)$であり、重みベクトル$winmathbbRn$は単位ベクトルである。 LTFの学習には3つの肯定的な結果が得られた。
  論文  参考訳（メタデータ） (2026-09-30T17:56:41Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• Algorithms for Sparse LPN and LSPN Against Low-noise [1.2143710013809321]
  ランダムノイズ(LPN)問題を伴う古典的学習環境のスパース変種を考察する。 我々の主な貢献は、LSPN(Learning Sparse Parities)問題とスパースCSP(SparseCSP)問題の両方に対して、低雑音に対する学習アルゴリズムを提供する新しいフレームワークである。
  論文  参考訳（メタデータ） (2024-07-27T08:57:04Z)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  有限混合系における非パラメトリック分布の学習問題について検討する。 このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
  論文  参考訳（メタデータ） (2022-03-28T23:53:48Z)
• 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)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。