論文の概要: Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach
- arxiv url: http://arxiv.org/abs/2408.16108v1
- Date: Wed, 28 Aug 2024 19:32:14 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-30 17:43:40.831471
- Title: Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach
- Title（参考訳）: Lagarias-Odlyzkoアルゴリズムによる平均型サブセットの最適化:モジュラ算術的アプローチ
- Authors: Antoine Joux, Karol Węgrzycki,
- Abstract要約: サブセット Sum 問題にモジュラー算術的アプローチを導入する。
本研究では,LLL削減基底ベクトルの長さを解析することにより,密度保証を向上できることを示す。
- 参考スコア（独自算出の注目度）: 3.0079490585515343
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Lagarias and Odlyzko (J.~ACM~1985) proposed a polynomial time algorithm for solving ``\emph{almost all}'' instances of the Subset Sum problem with $n$ integers of size $\Omega(\Gamma_{\text{LO}})$, where $\log_2(\Gamma_{\text{LO}}) > n^2 \log_2(\gamma)$ and $\gamma$ is a parameter of the lattice basis reduction ($\gamma > \sqrt{4/3}$ for LLL). The algorithm of Lagarias and Odlyzko is a cornerstone result in cryptography. However, the theoretical guarantee on the density of feasible instances has remained unimproved for almost 40 years. In this paper, we propose an algorithm to solve ``almost all'' instances of Subset Sum with integers of size $\Omega(\sqrt{\Gamma_{\text{LO}}})$ after a single call to the lattice reduction. Additionally, our argument allows us to solve the Subset Sum problem for multiple targets while the previous approach could only answer one target per call to lattice basis reduction. We introduce a modular arithmetic approach to the Subset Sum problem. The idea is to use the lattice reduction to solve a linear system modulo a suitably large prime. We show that density guarantees can be improved, by analysing the lengths of the LLL reduced basis vectors, of both the primal and the dual lattices simultaneously.
- Abstract（参考訳）: Lagarias and Odlyzko (J.~ACM~1985) は、subset Sum 問題の ``\emph{almost all}' のインスタンスを$n$の整数で解く多項式時間アルゴリズムを提案し、$\log_2(\Gamma_{\text{LO}}) > n^2 \log_2(\gamma)$ and $\gamma$ は格子基底還元$\gamma > \sqrt{4/3}$のパラメータである。
LagariasとOdlyzkoのアルゴリズムは暗号の基礎となる結果である。
しかし、実現可能なインスタンスの密度に関する理論的保証は、ほぼ40年間、未改善のままである。
本稿では、格子縮小への単一呼び出しの後に、$\Omega(\sqrt{\Gamma_{\text{LO}}})$\Omega(\sqrt{\Gamma_{\text{LO}}}) の整数で Subset Sum の `almost all'' のインスタンスを解くアルゴリズムを提案する。
さらに,従来の手法では1回のコールで1つのターゲットにしか答えられず,複数のターゲットに対するサブセット・サム問題を解くことができる。
サブセット Sum 問題にモジュラー算術的アプローチを導入する。
この考え方は、格子還元を用いて、線形系を好ましく大きな素数に変調する。
本研究では,LLL削減基底ベクトルの長さを一次格子と双対格子の両方で同時に解析することにより,密度保証を向上できることを示す。
関連論文リスト
- Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Fast algorithms for k-submodular maximization subject to a matroid
constraint [10.270420338235237]
マトロイド制約の下では、Threshold-Decreasing Algorithmを用いて$k$-submodular関数を最大化する。
我々は$k$-submodular関数に対して$(frac12 - epsilon)$-approximationアルゴリズムを与える。
論文 参考訳（メタデータ） (2023-07-26T07:08:03Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Linear Query Approximation Algorithms for Non-monotone Submodular
Maximization under Knapsack Constraint [16.02833173359407]
この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。
$mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
論文 参考訳（メタデータ） (2023-05-17T15:27:33Z) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax
Optimization [47.27237492375659]
双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。
Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
論文 参考訳（メタデータ） (2022-01-19T05:56:19Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。
第二に、完全適応部分モジュラリティの概念を導入する。
提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
論文 参考訳（メタデータ） (2020-07-08T15:54:28Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。