論文の概要: Solving the Shortest Vector Problem in $2^{0.6039n}$ Time via Mid-point Hessian
- arxiv url: http://arxiv.org/abs/2608.02478v2
- Date: Tue, 04 Aug 2026 03:43:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-05 13:15:27.437874
- Title: Solving the Shortest Vector Problem in $2^{0.6039n}$ Time via Mid-point Hessian
- Title（参考訳）: 2^{0.6039n}$時間における最短ベクトル問題の解法
- Authors: Minki Hhan,
- Abstract要約: 最短ベクトル問題(SVP)に対するランダム化アルゴリズムを提案する。
n$次元格子$mathcal L$に対して、我々のアルゴリズムは、古典的に20.6039n+o(n)$、量子的に20.5411n+o(n)$、空間的に20.5n+o(n)$でSVPを解く。
- 参考スコア（独自算出の注目度）: 3.891921282474929
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present randomized algorithms for the shortest vector problem (SVP). For the $n$-dimensional lattice $\mathcal L$, our algorithms solve SVP in time $2^{0.6039n+o(n)}$ classically and $2^{0.5411n+o(n)}$ quantumly and space $2^{0.5n+o(n)}$, improving the previous best algorithm running in $2^{n+o(n)}$ time and space of Aggarwal, Dadush, Regev, and Stephens-Davidowitz [STOC'15]. Our algorithms heavily use the property of the Hessian of the periodic Gaussian function at the half shortest vector: For a shortest vector $v \in \mathcal L$, the Hessian at $v/2$ has the eigenvector close to $v$, which can be used to recover $v$ using the (preprocessing) bounded distance decoding algorithm. Given the periodicity modulo $\mathcal L$, the candidate midpoints are indexed by the parity classes in $\mathcal L/2\mathcal L$. Our algorithm searches for the class of a shortest vector by estimating the corresponding Hessians using discrete Gaussian samples. We optimize the algorithm using random sublattice cosets and various sampling technique, achieving the final complexity. The optimization techniques may be of independent interest.
- Abstract（参考訳）: 本稿では,最短ベクトル問題(SVP)に対するランダム化アルゴリズムを提案する。
n 次元格子 $\mathcal L$ に対して、我々のアルゴリズムは、時間で 2^{0.6039n+o(n)}$ 古典的に 2^{0.5411n+o(n)$ 量子と空間で $2^{0.5n+o(n)$ を解き、以前の最高アルゴリズムを 2^{n+o(n)$ アガルワル、ダドゥーシュ、レゼフ、スティーブンス=ダヴィドヴィッツの時間と空間で改善する。
最短ベクトル$v \in \mathcal L$に対して、$v/2$のHessianは、$v$に近い固有ベクトルを持ち、(前処理)有界距離復号アルゴリズムを用いて$v$を復元することができる。
周期度 modulo $\mathcal L$ が与えられたとき、候補ミドルポイントは、$\mathcal L/2\mathcal L$ のパリティクラスによってインデックス付けされる。
本アルゴリズムは, 離散ガウスサンプルを用いて対応するヘッセンを推定することにより, 最短ベクトルのクラスを探索する。
ランダムな部分格子コセットと様々なサンプリング手法を用いてアルゴリズムを最適化し,最終的な複雑性を実現する。
最適化技術は独立した関心を持つかもしれない。
関連論文リスト
- Quantum Algorithms for Projection-Free Sparse Convex Optimization [32.34794896079469]
ベクトル領域に対しては、$O(sqrtd/varepsilon)$のクエリ複雑性を持つ$varepsilon$-optimal解を求めるスパース制約に対する2つの量子アルゴリズムを提案する。
行列領域に対しては、時間複雑性を$tildeO(rd/varepsilon2)$と$tildeO(sqrtrd/varepsilon3)$に改善する2つの核ノルム制約の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-07-11T12:43:58Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。
我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
論文 参考訳（メタデータ） (2024-03-07T18:23:51Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Do you know what q-means? [42.96240569413475]
古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。
また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - 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) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - A Faster $k$-means++ Algorithm [11.428775569173638]
ほぼ最適な実行時間で$k$-means++問題を解決するアルゴリズムを提案する。
我々は、$widetildeO(nd + nk2)$時間しかかからない新しいアルゴリズムtextscFastKmeans++を提案する。
論文 参考訳（メタデータ） (2022-11-28T08:17:12Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding [4.5686700995634055]
最短ベクトル問題(SVP)に対する証明可能な古典量子アルゴリズムの新しいアルゴリズムを提案する。
SVPの新しいアルゴリズムは、時間複雑性とメモリ要求の間のスムーズなトレードオフを提供する。
20.950n+o(n)$で動作し、20.5n+o(n)$クラシックメモリとポリ(n)量子ビットを必要とするSVPの量子アルゴリズム。
論文 参考訳（メタデータ） (2020-02-19T01:38:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。