論文の概要: MergeLLL: A Hierarchical Divide-and-Conquer Framework for LLL-Based Lattice Reduction

• arxiv url: http://arxiv.org/abs/2606.26784v1
• Date: Thu, 25 Jun 2026 09:20:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-26 18:46:32.224725
• Title: MergeLLL: A Hierarchical Divide-and-Conquer Framework for LLL-Based Lattice Reduction
• Title（参考訳）: MergeLLL: LLLベースの格子リダクションのための階層的除算型フレームワーク
• Abstract要約: 格子基底還元アルゴリズムは、計算数理論や格子ベースの暗号に様々な応用がある。 マージソートとPotLLLスタイルの深い挿入を組み込んだマージソートとコンカマーの分離戦略により,mergeLLLを提案する。 このフレームワークでは、格子基底をサブベースに分割し、局所還元を独立に行い、階層的なマージによって全基底を再構築する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Lattice basis reduction algorithms have various applications in computational number theory and lattice-based cryptography, but their complexity increases rapidly with the dimension. Motivated by the divide-and-conquer strategy of merge sort and incorporating PotLLL-style deep insertions during recombination, MergeLLL is proposed. In this framework, a lattice basis is split into sub-bases, local reductions are performed independently, and the full basis is reconstructed through hierarchical merging. The approach is focused on improving local lattice structure first before global basis properties are refined, resulting in enhanced Gram-Schmidt orthogonality and numerical stability, while overall computational cost is reduced. The method is naturally parallelizable, allowing efficient multicore and distributed execution. It is shown that the reduction and merging steps preserve the lattice structure through unimodular transformations and achieve logarithmic parallel depth. In experiments on subset-sum and NTRU-derived lattices, improvements over classical lattice reduction algorithms are demonstrated, including better orthogonality, a reduced number of expensive swap operations, and an improved Hermite factor, indicating higher-quality reduced bases.
• Abstract（参考訳）: 格子基底還元アルゴリズムは計算数理論や格子ベースの暗号に様々な応用があるが、その複雑さは次元とともに急速に増大する。 マージソートとPotLLLスタイルの深い挿入を組み込んだマージソートとコンカマーの分離戦略により,mergeLLLを提案する。 このフレームワークでは、格子基底をサブベースに分割し、局所還元を独立に行い、階層的なマージによって全基底を再構築する。 この手法は、グローバル基底特性が洗練される前に局所格子構造を改善することに重点を置いており、結果としてグラマーシュミット直交と数値安定性が向上し、全体的な計算コストが低減される。 この方法は自然に並列化可能であり、効率的なマルチコアおよび分散実行を可能にする。 その結果, 単モジュラー変換により格子構造を保ち, 対数平行深さを達成できることが示唆された。 サブセットサムおよびNTRU由来格子の実験では、直交性の向上、高価なスワップ操作の削減、Hermite因子の改善など、古典的格子削減アルゴリズムの改善が示されている。

関連論文リスト

• TopoLS: Lattice Surgery Compilation via Topological Program Transformations [6.387941081167297]
  TopoLSは、ZX-ダイアグラム最適化とモンテカルロ木探索を組み合わせたトポロジカルコンパイラである。 SAT-solverベースのコンパイラと比較して、TopoLSは格子サージェリーコンパイルに効果的でスケーラブルなソリューションを提供する。
  論文  参考訳（メタデータ） (2026-01-30T15:54:57Z)
• Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe [61.68406997155879]
  State-of-the-art Large Language Model (LLM) プルーニング手法は階層的に動作し、階層ごとのプルーニングエラーを最小限に抑え、完全な再トレーニングを回避する。 既存の手法は、刈り上げ対象の重量相互作用を無視する欲求凸に依存する。 提案手法は, 層ごとのプルーニング誤差を大幅に低減し, 最先端のGPTアーキテクチャにおいて高いベースラインを達成し, メモリ効率を保っている。
  論文  参考訳（メタデータ） (2025-10-15T16:13:44Z)
• An Accelerated Alternating Partial Bregman Algorithm for ReLU-based Matrix Decomposition [0.0]
  本稿では,非負行列上に補正されたスパース低ランク特性について検討する。 本稿では,クラスタリングと圧縮タスクに有用な構造を取り入れた新しい正規化項を提案する。 我々は、任意の$Lge 1$に対して常に持つ$L$-smoothプロパティを維持しながら、対応する閉形式解を導出する。
  論文  参考訳（メタデータ） (2025-03-04T08:20:34Z)
• A GPU-Accelerated Bi-linear ADMM Algorithm for Distributed Sparse Machine Learning [4.258375398293221]
  Bi-cADMMは、計算ノードのネットワーク上で定義された大規模正規化されたスパース機械学習問題を解決することを目的としている。 Bi-cADMMはParallel Sparse Fitting Toolboxと呼ばれるオープンソースのPythonパッケージで実装されている。
  論文  参考訳（メタデータ） (2024-05-25T15:11:34Z)
• Neural Lattice Reduction: A Self-Supervised Geometric Deep Learning Approach [12.679411410749521]
  本稿では,ニューラルネットワークによる格子縮小問題に対するアルゴリズム空間のパラメータ化と,教師付きデータを持たないアルゴリズムの探索を行うことが可能であることを示す。 本研究では,一様行列の因子を出力する深層ニューラルネットワークを設計し,非直交格子基底をペナルライズして自己指導的に学習する。 提案手法は,一連のベンチマークにおいて,Lenstra-Lenstra-Lov'aszアルゴリズムに匹敵する複雑性と性能を持つアルゴリズムが得られることを示す。
  論文  参考訳（メタデータ） (2023-11-14T13:54:35Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothness [0.0]
  非常に多くのスムーズで可能な非サイズの関数の平均を考慮し、この問題に対処するために2つの広く最小限のフレームワークを使用します。 IG/RRスキームの簡易制御による修正を定義する。 我々は、完全なバッチ勾配(L-BFGS)とIG/RR手法の実装の両方で実装を証明し、アルゴリズムが同様の計算作業を必要とすることを証明した。
  論文  参考訳（メタデータ） (2022-12-04T15:26:36Z)
• Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming [1.3053649021965603]
  最小二乗クラスタリング(MSSC)は、最近、各クラスタの濃度に関する事前知識を活用するために拡張されている。 本稿では,分枝切断法に基づく大域的最適化手法を提案する。 上界に対して、各ノードで解いたSDP緩和の解を生かした局所探索手順を提案する。
  論文  参考訳（メタデータ） (2022-09-19T10:19:06Z)
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning [58.91954425047425]
  本稿では,分散学習における部分トラグラーの緩和を目的とした,新たな勾配符号化方式を提案する。 L の符号パラメータを L に表わした勾配座標符号化方式を提案する。
  論文  参考訳（メタデータ） (2022-06-06T09:25:40Z)
• Communication-Efficient Federated Learning via Quantized Compressed Sensing [82.10695943017907]
  提案フレームワークは,無線機器の勾配圧縮とパラメータサーバの勾配再構成からなる。 勾配スペーシフィケーションと量子化により、我々の戦略は1ビット勾配圧縮よりも高い圧縮比を達成することができる。 圧縮を行わない場合とほぼ同じ性能を実現できることを示す。
  論文  参考訳（メタデータ） (2021-11-30T02:13:54Z)
• Poly-NL: Linear Complexity Non-local Layers with Polynomials [76.21832434001759]
  性能を損なわずに2次から線形に複雑性を低減できる新しい高速非局所ブロックを定式化する。 The proposed method, we dub that "Poly-NL" is competitive to state-of-the-art performance across image recognition, instance segmentation, and face detection task。
  論文  参考訳（メタデータ） (2021-07-06T19:51:37Z)
• Gradient Boosted Binary Histogram Ensemble for Large-scale Regression [60.16351608335641]
  本研究では,2値ヒストグラム分割とアンサンブル学習に基づくテキストグラディエント2値ヒストグラムアンサンブル(GBBHE)と呼ばれる大規模回帰問題に対する勾配向上アルゴリズムを提案する。 実験では, 勾配向上回帰木 (GBRT) などの他の最先端アルゴリズムと比較して, GBBHEアルゴリズムは大規模データセット上での実行時間が少なく, 有望な性能を示す。
  論文  参考訳（メタデータ） (2021-06-03T17:05:40Z)
• A Parallelizable Lattice Rescoring Strategy with Neural Language Models [62.20538383769179]
  自動音声認識のためのニューラルネットワークモデル(LM)を用いた効率的な格子相関のための後部格子拡張アルゴリズムを提案する。 スイッチボードデータセットにおける実験により,提案手法が同等の認識性能を得た。 PyTorchで訓練されたニューラル LM をKaldi との格子再構成に簡単に統合することで、並列再描画法により柔軟性が向上する。
  論文  参考訳（メタデータ） (2021-03-08T21:23:12Z)
• Feature Whitening via Gradient Transformation for Improved Convergence [3.5579740292581]
  機能白化の複雑さの欠点に対処する。 サンプル変換を重み勾配への変換によって置き換える等価な手法をBサンプルの各バッチに適用する。 CIFAR と Imagenet データセットで実証された画像分類のためのResNet ベースのネットワークを用いて提案アルゴリズムを例示する。
  論文  参考訳（メタデータ） (2020-10-04T11:30:20Z)

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

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