論文の概要: Asymptotics of Random-Lattice Enumeration: Beyond HKZ via Dense Sublattices

• arxiv url: http://arxiv.org/abs/2610.15265v1
• Date: Sun, 11 Oct 2026 01:26:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-20 01:51:40.291437
• Title: Asymptotics of Random-Lattice Enumeration: Beyond HKZ via Dense Sublattices
• Title（参考訳）: ランダム格子列挙の漸近:Dense SublatticesによるHKZを超えて
• Abstract要約: 我々は、$n$次元のハールランダム格子上の(未開の)列挙木のサイズについて検討する。 準HKZ基底に対しては、ランダム格子HKZ幾何を厳密に解析する。 上界に対しては、高い確率で高密度原始半ランク部分格子が存在することを示す。
• 参考スコア（独自算出の注目度）: 0.40611352512781856
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: To bridge the gap between worst-case and heuristic analyses of lattice enumeration, we study the sizes of (unpruned) enumeration trees on $n$-dimensional Haar-random lattices. Writing $n^{cn+o(n)}$ for the tree size at the shortest vector radius, we investigate the asymptotic scaling of $c$, and which bases minimize it. For quasi-HKZ bases, we rigorously analyze the random-lattice HKZ geometry and establish $c=1/(2e)\approx 0.1839$. This matches the worst-case enumeration exponent of Hanrot-Stehlé and confirms earlier predictions for the geometry of HKZ bases on random lattices. Searching beyond quasi-HKZ bases, we prove that with high probability, the minimum achievable tree size exponent $c$ over all bases of a random lattice satisfies: \begin{align} 0.1464 \approx \frac{2-\sqrt{2}}{4}\leq c<0.1474. \end{align} For the lower bound, we use Kim's mean-value formula for nested chains of primitive sublattices to rule out bases with small prefix determinants. This strengthens the earlier Rankin-based heuristic lower bound exponent $c \geq 1/8$, discussed by Nguyen and Hanrot-Stehlé, and rules out the existence of random-lattice bases with trees as small as predicted by the geometric series assumption. For the upper bound, we show that with high probability a dense primitive half-rank sublattice exists with determinant at most $n^{n/8 + o(n)}$. Combining dual HKZ on this sublattice with HKZ on its quotient gives a basis with $c \leq 1/(4\sqrt{e}) \approx 0.1516$. Recursively splitting each half lowers the upper bound below $0.1474$, and under a natural heuristic assumption we prove that the lower bound is tight. Combined with the collision search of Feng-Gao-Liu, our two-block construction gives a polynomial-space algorithm solving the closest vector problem with preprocessing (CVPP) on random lattices in query time $n^{0.0892 n + o(n)}$ for arbitrary targets.
• Abstract（参考訳）: 最悪のケースと格子列挙のヒューリスティック解析の間のギャップを埋めるために、$n$次元のハールランダム格子上の(未開の)列挙木のサイズについて検討する。 最短ベクトル半径における木の大きさについて、$n^{cn+o(n)}$を書き、その漸近スケーリングを$c$で調べ、どの基底を最小化するかを検討する。 準HKZ基底に対しては、ランダム格子HKZ幾何を厳密に解析し、$c=1/(2e)\approx 0.1839$とする。 これはHanrot-Stehléの最悪の列挙指数と一致し、ランダム格子上のHKZ基底の幾何学に関する以前の予測を確認する。 準-HKZ基底を越えて探索すると、確率の高い場合には、ランダム格子のすべての基底上の到達可能な木の大きさ指数$c$が成り立つ: \begin{align} 0.1464 \approx \frac{2-\sqrt{2}}{4}\leq c<0.1474。 以下に示すように、Kim の平均値式を、プリミティブな部分格子のネスト鎖に使用して、小さなプレフィックス行列式で基底を除外する。 これは、Nguyen と Hanrot-Stehlé によって議論された初期のランキンベースのヒューリスティックな下界指数 $c \geq 1/8$ を強化し、幾何学的級数仮定によって予測されるほど小さい木を持つランダム格子基底の存在を規定する。 上界について、高確率では、高次原始半ランク部分格子が存在し、行列式は最大$n^{n/8 + o(n)}$である。 この部分格子上の双対 HKZ と商上の HKZ を組み合わせると、$c \leq 1/(4\sqrt{e}) \approx 0.1516$ となる。 帰納的分割は上界を0.1474$以下に下げ、自然なヒューリスティックな仮定の下で下界が厳密であることを証明する。 Feng-Gao-Liu の衝突探索と組み合わせ、我々の2ブロック構成は、任意のターゲットに対して、クエリ時間$n^{0.0892 n + o(n)}$でランダム格子上の前処理(CVPP)で最も近いベクトル問題を解く多項式空間アルゴリズムを与える。

関連論文リスト

• Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
  凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。 学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。 定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
  論文  参考訳（メタデータ） (2026-09-30T18:26:29Z)
• Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs [0.0]
  非空コンパクト集合 $mathcal X の部分集合 Rd$ 上で、決定論的目的関数 $f$ を最小化するための期待された改善 (EI) ポリシーについて検討する。
  論文  参考訳（メタデータ） (2026-07-31T10:18:54Z)
• Tight Sample Bounds for Renyi and Min-Entropy Estimation [4.866431869728017]
  サンプルからエントロピーを推定することは、情報理論とプロパティテストにおいて基礎となる。 定数加法精度に対する最小エントロピー推定が標本複雑性$(klog k)$であることを証明する。
  論文  参考訳（メタデータ） (2026-07-18T21:01:38Z)
• Module Lattice Security (Part III): Structured CVP Distance on the Log-Unit Lattice [1.0152838128195467]
  ランダム短環要素から対数単位格子への$L2$CVP距離が$frac2sqrt6sqrtn$ as $n=2k-1toinfty$に収束することを示す。 Linfty$ノルムに対して、$n$以下のガウス座標の最大値は$O(sqrtlog n)$となり、短発生問題に対する多項式近似係数に変換される。
  論文  参考訳（メタデータ） (2026-05-17T12:00:59Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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