Fugu-MT 論文翻訳(概要): Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space

論文の概要: Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space

arxiv url: http://arxiv.org/abs/2611.07313v1
Date: Thu, 05 Nov 2026 01:59:14 GMT
ステータス: 翻訳完了
システム内更新日: 2026-11-06 21:50:50.487243
Title: Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space
Title（参考訳）: Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space
Abstract要約: 任意の整数 $pge2$ に対して、厳密な $ell_p$CVP から正則境界への階数保存的還元を与える。すべての固定整数$pge3$に対して、同じ還元は任意の有理目標に対する正確な$ell_p$アルゴリズムをもたらす。
参考スコア（独自算出の注目度）: 7.327645708857432
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We give a randomized, rank-preserving reduction from exact $\ell_p$-CVP to exact Euclidean SVP for every integer $p\ge2$. For rational inputs of bit length $\ell$ on full-rank lattices $L\subset\mathbb R^N$, the reduction uses $(Cp)^N\poly(p,\ell)$ oracle calls and additional bit operations, where $C$ is an absolute constant. It uses $\poly(p,\ell)$ working space outside the oracle, and all oracle queries have rank $N$ and $\poly(p,\ell)$ bit complexity. For $p=2$, the reduction transfers polynomial-space exact SVP algorithms to exact CVP with $2^{O(N)}\poly(\ell)$ time overhead. Instantiating it with the SVP algorithms of Kannan and of Feng, Gao and Liu yields randomized polynomial-space CVP algorithms running in time $N^{N/(2e)+o(N)}$ and $N^{N/(4e)+o(N)}$, respectively. For every fixed integer $p\ge3$, the same reduction yields exact $\ell_p$-CVP algorithms for arbitrary rational targets either in randomized time and space $2^{O(N)}$, or in randomized time $N^{N/(4e)+o(N)}$ and polynomial space. These algorithmic bounds are up to polynomial factors in $\ell$. The reduction performs local search sequentially over the cosets of $2L$, where $L$ is the input lattice, while tracking the excess of the current objective value over the optimum. Within a coset containing a closest vector, midpoint inequalities bound the unknown correction in terms of this excess, which in turn allows us to construct many short corrections that reduce the excess bound by a factor of four. A counting argument shows that these improving corrections form a sufficiently large fraction of the lattice points in a known search region, and a sparsification-based sampler assigns sufficiently large probability to every nonzero vector in that region, using at most one SVP call per sample. For $p\ge3$, the same framework is extended using a diagonal weighted norm computed from the current point.
Abstract（参考訳）: 任意の整数 $p\ge2$ に対して、正確な $\ell_p$-CVP から正確な Euclidean SVP へのランダム化、階数保存の還元を与える。ビット長$\ell$をフルランク格子上で有理入力する場合、$L\subset\mathbb R^N$ は $(Cp)^N\poly(p,\ell)$ oracle コールと追加ビット演算を使用し、$C$ は絶対定数である。オラクルの外の作業スペースは$\poly(p,\ell)$で、全てのオラクルクエリはランクが$N$と$\poly(p,\ell)$bitである。 p=2$ の場合、この還元は多項式空間の正確な SVP アルゴリズムを 2,^{O(N)}\poly(\ell)$ 時間オーバーヘッドを持つ正確な CVP に転送する。カンナンのSVPアルゴリズムとFeng, Gao, LiuのSVPアルゴリズムを併用すると、ランダム化された多項式空間CVPアルゴリズムがそれぞれ$N^{N/(2e)+o(N)}$と$N^{N/(4e)+o(N)}$で実行される。任意の固定整数 $p\ge3$ に対して、同じ還元は、ランダム化された時間と空間 2^{O(N)}$ またはランダム化された時間 $N^{N/(4e)+o(N)}$ と多項式空間の任意の有理的対象に対して、正確な$\ell_p$-CVPアルゴリズムを得る。これらのアルゴリズム的境界は$\ell$の多項式因子である。この縮小は、(L) が入力格子である $2L) の余集合上で連続的に局所探索を行い、同時に、現在の目標値の過大な値を最適に追跡する。最も近いベクトルを含む余集合の中では、中間点の不等式は、この余剰量の観点から未知の補正を束縛し、従って、余剰を 4 の係数で減少させる多くの短い補正を構成できる。カウントする議論は、これらの補正が既知の探索領域の格子点の十分大きな部分を形成し、スパーシフィケーションに基づくサンプルは、少なくとも1つのSVP呼び出しを用いて、その領域のすべての非ゼロベクトルに十分に大きな確率を割り当てていることを示している。 \(p\ge3$ の場合、同じフレームワークは現在の点から計算された対角的重み付きノルムを用いて拡張される。

論文の概要: Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space

関連論文リスト