論文の概要: Sample-Preserving Search-to-Decision Reduction for Noisy Linear Equations over Large Moduli

• arxiv url: http://arxiv.org/abs/2610.12913v1
• Date: Fri, 09 Oct 2026 03:04:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-13 04:06:29.364392
• Title: Sample-Preserving Search-to-Decision Reduction for Noisy Linear Equations over Large Moduli
• Title（参考訳）: 大規模モジュラー上での雑音線形方程式のサンプル保存探索-決定還元
• Abstract要約: 雑音線形方程式の問題は、雑音評価が与えられた有限体上のランダム線型系に対する解を求めることである。 これは、Learning with Errors(LWE)、Learning with Rounding(LWR)、Learning Parity with Noise(LPN)など、暗号化で広く使われている様々な学習問題の一般化である。 複素数$mathrmpoly(n,m,log q, q/)$を持つ雑音線形方程式に対する新しいサンプル保存型探索-決定還元法を提案する。
• 参考スコア（独自算出の注目度）: 3.587583295683848
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Noisy Linear Equations problem involves finding the solution to a random linear system over a finite field given noisy evaluations. This is a generalisation of various learning problems widely used in cryptography, including Learning with Errors (LWE), Learning with Rounding (LWR), and Learning Parity with Noise (LPN). We present a new sample-preserving search-to-decision reduction for Noisy Linear Equations that has complexity $\mathrm{poly}(n,m,\log q, q/σ)$, where $n$ is the dimension of the secret, $m$ is the number of samples, $q$ is the modulus, and $σ$ is the magnitude of the noise (defined suitably for the kind of noise involved). In particular, this implies search-to-decision reductions for LWE and LWR that run in time $\mathrm{poly}(n)$ even if the modulus $q$ is exponentially large, as long as the noise-to-modulus ratio $σ/q$ is non-negligible. Our reduction works for prime moduli $q$. If $q$ is composite, it instead produces a list that contains a small multiple of the solution. Prior to this work, known search-to-decision reductions for LWE and LWR either did not preserve the parameters of the problem (i.e., $m$, $n$, $σ$, and $q$), or had complexity that scaled polynomially with either $σ$ or the largest prime factor of $q$.
• Abstract（参考訳）: 雑音線形方程式の問題は、雑音評価が与えられた有限体上のランダム線型系の解を求めることである。 これは、Learning with Errors(LWE)、Learning with Rounding(LWR)、Learning Parity with Noise(LPN)など、暗号化で広く使われているさまざまな学習問題の一般化である。 複素数$\mathrm{poly}(n,m,\log q, q/σ)$, where $n$ is the dimension of the secret, $m$ is the number of sample, $q$ is the modulus, $σ$ is the size of the noise(関係するノイズの種類に好適に定義される)。 特にこれは、ノイズ・ツー・モーラス比$σ/q$が非無視である限り、時として$\mathrm{poly}(n)$が指数関数的に大きいとしても、LWE と LWR に対する探索-決定の減少を意味する。 我々の還元は素モジュライ$q$に対して作用する。 もし$q$が合成であるなら、代わりに、ソリューションの小さな倍数を含むリストを生成する。 この研究に先立ち、LWE と LWR の既知の探索-決定還元は問題のパラメータ(例えば $m$, $n$, $σ$, $q$)を保存しなかったか、あるいは$σ$ あるいは$q$ の最大の素因子で多項式的にスケールした複雑性を持っていた。

関連論文リスト

• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models [34.196233651364615]
  ガウス分布に基づく実数値マルチインデックスモデル(MIM)の学習の複雑さについて検討する。 K$-MIM は関数 $f:mathbbRdto mathbbR$ であり、入力の$K$-次元部分空間への射影のみに依存する。 逆ラベルノイズが存在する場合でも, 正方形損失に対して幅広いMIMを学習するための一般アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-05-27T17:47:26Z)
• A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise [36.29182619215646]
  我々は、マスアートノイズの存在下で、PACが$gamma$-marginハーフスペースを学習する際の問題について検討する。 我々のアルゴリズムは単純で実用的であり、慎重に選択された凸損失の列にオンラインSGDを頼っている。
  論文  参考訳（メタデータ） (2025-01-16T17:44:18Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。 我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
  論文  参考訳（メタデータ） (2023-06-28T16:33:39Z)
• Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes [5.526935605535376]
  ノイズの多いサンプルから単純さを学習するために、サンプルの複雑さが結びついているのがわかります。 我々は、$mathrmSNRgeOmegaleft(K1/2right)$ である限り、ノイズのないシステムのサンプルの複雑さは、ノイズのないケースのそれと同じ順序であることを示す。
  論文  参考訳（メタデータ） (2022-09-09T23:35:25Z)
• 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)

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

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