論文の概要: Gaussian Difference Dynamics: Breaking the $2^{n/2}$ Barrier for the Shortest Vector Problem and Discrete Gaussian Sampling

• arxiv url: http://arxiv.org/abs/2611.04336v1
• Date: Tue, 03 Nov 2026 05:22:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-10 02:28:10.992184
• Title: Gaussian Difference Dynamics: Breaking the $2^{n/2}$ Barrier for the Shortest Vector Problem and Discrete Gaussian Sampling
• Title（参考訳）: ガウス差分ダイナミクス:最短ベクトル問題と離散ガウスサンプリングに対する$2^{n/2}$バリアを破る
• Abstract要約: 離散ガウスサンプリングと最短ベクトル問題に対する古典的ランダム化アルゴリズムを提案する。 すべての固定$>1$に対して、幅$ge_1/2(L)$で任意の格子上のDGSは$$3/2)n/2+o(n)text time qquadtextandqquad (4/3)n/2+o(n)text spaceを取る。 任意の格子に対して、我々のアルゴリズムは20.4130n+o(n) テキストで確率の高い最短の非ゼロベクトルを返す。
• 参考スコア（独自算出の注目度）: 1.9485627909326053
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give classical randomized algorithms in a word RAM model that break the $2^{n/2}$ barrier for both discrete Gaussian sampling (DGS) and the Shortest Vector Problem (SVP). For every fixed $α>1$, shifted DGS on arbitrary lattices at width $σ\geαη_{1/2}(L)$ takes $$ (3/2)^{n/2+o(n)}\text{ time} \qquad\text{and}\qquad (4/3)^{n/2+o(n)}\text{ space}. $$ These bounds match the Becker--Ducas--Gama--Laarhoven (BDGL) heuristic sieving exponents. At widths at least $3η_{1/2}(L)/2$, the same total cost suffices for an entire batch of $\lfloor(4/3)^{n/2}\rfloor$ samples jointly close to independent target Gaussians. For SVP on arbitrary lattices, our algorithm returns a shortest nonzero vector with high probability in $$ 2^{0.4130n+o(n)}\text{ time} \qquad\text{and}\qquad 2^{0.3138n+o(n)}\text{ space}. $$ As a corollary, we obtain centered DGS at every width with the same exponents, answering a question of Stephens-Davidowitz (SODA 2016). We introduce Gaussian difference dynamics (GDD), a framework for tracking expected counts and pairwise clustering of vectors through repeated differencing. A closed recursion for the first two counting moments controls these quantities relative to a Gaussian reference, without requiring independence within intermediate lists. Accurate moment bounds let us extract a Gaussian sample by weighted selection, while the weaker bounds needed to establish a shortest vector representation allow us to retain more differences. We perform these transitions on thin spherical shells, where the Gaussian rejection weights can be renormalized at subexponential cost. For batch sampling, we combine this geometry with the double rejection technique of Doulgerakis and Laarhoven to control the joint distribution of outputs while reusing vectors.
• Abstract（参考訳）: 離散ガウスサンプリング (DGS) と最短ベクトル問題 (SVP) の両方の障壁を突破するワードRAMモデルに古典的ランダム化アルゴリズムを与える。 すべての固定$α>1$に対して、幅$σ\geαη_{1/2}(L)$は$3/2)^{n/2+o(n)}\text{time} \qquad\text{and}\qquad (4/3)^{n/2+o(n)}\text{ space} を取る。 これらのバウンドは、Becker--Ducas--Gama--Laarhoven (BDGL)ヒューリスティックなSieving exponentsと一致する。 少なくとも3η_{1/2}(L)/2$の幅では、$\lfloor(4/3)^{n/2}\rfloor$サンプルの合計コストは、独立ターゲットガウスに近接している。 任意の格子上のSVPに対して、我々のアルゴリズムは、$ 2^{0.4130n+o(n)}\text{time} \qquad\text{and}\qquad 2^{0.3138n+o(n)}\text{ space} の確率の低い最短ゼロベクトルを返す。 関連記事:$$$ a corollary, we obtain a centered DGS at every width with the same exponents, answering a question of Stephens-Davidowitz (SODA 2016)。 本稿では,予測数を追跡するフレームワークであるガウス差分ダイナミクス(GDD)と,繰り返しの差分によるベクトルのペアクラスタリングを紹介する。 最初の2つの計数モーメントの閉再帰は、中間リスト内で独立性を必要としないガウス参照に対するこれらの量を制御する。 正確なモーメント境界は、重み付けされた選択によってガウスサンプルを抽出するが、最短ベクトル表現を確立するのに必要なより弱い境界は、より多くの差を維持することができる。 我々はこれらの遷移を細い球殻上で行い、そこではガウスの拒絶重みを指数以下のコストで再正規化することができる。 バッチサンプリングでは、この幾何学とDoullgerakisとLaarhovenの二重拒否手法を組み合わせて、ベクトルを再利用しながら出力の結合分布を制御する。

関連論文リスト

• Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace [0.0]
  我々は、最大で1/3$の誤差を持つ$mathbb Rn$におけるベクトル-in-Subspaceのランダム化通信複雑性が$(sqrt n)$であることを証明する。 正確なワンウェイ量子プロトコルは$O(log n)$ qubitsを使用しており、対話型古典通信よりも指数的量子優位性の幾何学的な例である。
  論文  参考訳（メタデータ） (2026-10-21T17:12:19Z)
• Gaussian Approximation of Besov Functions for Logistic Classification on Manifolds [4.74753940673406]
  連結コンパクトな滑らかな埋め込み多様体上での近似と正規化ロジスティック分類について検討する。 2つの大きな課題は、有界ベイズ函数を仮定せずに高速不等式を導出することである。 飽和を伴わない固有次元と対象の正則性の両方を利用する近似式を構築した。
  論文  参考訳（メタデータ） (2026-10-19T14:26:27Z)
• Smooth Sailing through Spherical Shells: Provable Random-Lattice Sieving in Time $2^{0.292n}$ [0.3437656066916039]
  ハールランダムな一モジュラー格子上の格子 我々は、Haar-random 格子上での Sieving と同じ複雑さを確実に達成できることを示す。
  論文  参考訳（メタデータ） (2026-09-26T22:07:05Z)
• Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee [12.89814955033651]
  ランダム化されたスケッチと解法アルゴリズムは、入力を小さな問題に置き換えることで、過剰に制約された$ell$レグレッションを加速する。 我々のスケッチは$ell_infty$ guarantee with $m=O(-2dlog d)$ rows, using one Hadamard pass with a padded internal dimension $N=widetildeO(n+-2d3)$, and is effective to apply。
  論文  参考訳（メタデータ） (2026-08-27T02:43:30Z)
• The Wristband Gaussian Loss: Deterministic, Composable Latents via a Sphere-Interval Decomposition [1.0195618602298684]
  リストバンドガウス損失(英: Wristband Gaussian Loss)は、サンプリング、KL項、反復輸送のないガウス化点埋め込みに対する決定論的バッチ損失である。 我々は、この反射カーネルの目的を、2つの方法で計算する:$O(N2 d)$で最寄りの3イメージのペアランケーションと、角およびラジアルマーサーモードに結合するスペクトルノイマン経路である。 1Dワッサーシュタインの半径項とモーメントペナルティは同じ最適値を持つ有限サンプル加速器として機能し、モンテカルロ$はこれらの成分を単一の標準統計量に変換する。
  論文  参考訳（メタデータ） (2026-05-09T07:25:37Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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