論文の概要: On Wagner's k-Tree Algorithm Over Integers

• arxiv url: http://arxiv.org/abs/2410.06856v1
• Date: Thu, 10 Oct 2024 05:55:21 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-31 23:47:07.808922
• Title: On Wagner's k-Tree Algorithm Over Integers
• Title（参考訳）: 整数上のワグナーのk-Treeアルゴリズムについて
• Authors: Haoxing Lin, Prashant Vasudevan,
• Abstract要約: k-Tree は平均ケース k-SUM 問題に対する非自明なアルゴリズムである。 入力リストのサイズがこれよりもかなり大きい場合、高い確率で成功することを示す。
• 参考スコア（独自算出の注目度）: 1.795561427808824
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: The k-Tree algorithm [Wagner 02] is a non-trivial algorithm for the average-case k-SUM problem that has found widespread use in cryptanalysis. Its input consists of k lists, each containing n integers from a range of size m. Wagner's original heuristic analysis suggested that this algorithm succeeds with constant probability if n = m^{1/(\log{k}+1)}, and that in this case it runs in time O(kn). Subsequent rigorous analysis of the algorithm [Lyubashevsky 05, Shallue 08, Joux-Kippen-Loss 24] has shown that it succeeds with high probability if the input list sizes are significantly larger than this. We present a broader rigorous analysis of the k-Tree algorithm, showing upper and lower bounds on its success probability and complexity for any size of the input lists. Our results confirm Wagner's heuristic conclusions, and also give meaningful bounds for a wide range of list sizes that are not covered by existing analyses. We present analytical bounds that are asymptotically tight, as well as an efficient algorithm that computes (provably correct) bounds for a wide range of concrete parameter settings. We also do the same for the k-Tree algorithm over Z_m. Finally, we present experimental evaluation of the tightness of our results.
• Abstract（参考訳）: k-Tree アルゴリズム [Wagner 02] は、暗号解析において広く用いられている平均ケース k-SUM 問題に対する非自明なアルゴリズムである。 入力は k 個のリストで構成され、それぞれサイズ m の n 個の整数を含む。 ワグナーの元々のヒューリスティック解析は、このアルゴリズムが n = m^{1/(\log{k}+1)} であれば一定の確率で成功し、この場合時間 O(kn) で実行されることを示唆している。 その後のアルゴリズムの厳密な分析 (Lyubashevsky 05, Shallue 08, Joux-Kippen-Loss 24] により、入力リストのサイズがこれよりもかなり大きい場合、高い確率で成功することを示した。 我々は、k-Treeアルゴリズムのより厳密な解析を行い、入力リストの任意のサイズに対して、その成功確率と複雑性の上限を上下に示す。 我々の結果は、ワグナーのヒューリスティックな結論を確認し、既存の分析ではカバーされていない幅広いリストサイズに有意義な境界を与える。 本稿では, 漸近的に厳密な解析的境界と, 幅広い具体的パラメータ設定に対して(確実に正しい)境界を計算する効率的なアルゴリズムを提案する。 また、Z_m 上の k-Tree アルゴリズムも同様に行う。 最後に,実験結果の厳密さを実験的に評価した。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
  ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。 A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-08-23T08:38:53Z)
• Universal Quantum Speedup for Branch-and-Bound, Branch-and-Cut, and Tree-Search Algorithms [13.152347996965297]
  混合プログラム(MIP)は、コンピュータサイエンス、オペレーションリサーチ、ファイナンシャルエンジニアリングに関心を持つ多くの最適化問題をモデル化する。 Branch-and-Cutアルゴリズムは、ブランチ・アンド・バウンド論理とカットプレーンルーチンを組み合わせることで、現代のMIPソルバのコアとなる。 本稿では,古典的分岐と境界のアルゴリズムを用いた量子アルゴリズムIncremental-Quantum-Branch-and-Boundを提案する。
  論文  参考訳（メタデータ） (2022-10-06T21:08:46Z)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。 我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
  論文  参考訳（メタデータ） (2022-06-07T16:49:54Z)
• Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR [10.391533135772699]
  a average-case variant of a $k$-SUM conjecture(英語版)は、$r$乱数のリストで 0 に等しい数を見つけることは $rlceil k/2 rceil$ time よりもはるかに少ない。 リストがより多くの数を持ち、多くの解が存在する高密度なパラメータ体系では、その中の1つを見つける複雑さは、ワーグナーの$k$-treeアルゴリズムによって著しく改善される。
  論文  参考訳（メタデータ） (2021-10-31T13:03:36Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
  量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。 本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
  論文  参考訳（メタデータ） (2021-05-18T06:51:11Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Exact Quantum Query Algorithms Outperforming Parity -- Beyond The Symmetric functions [3.652509571098291]
  まず、$Omega left(2fracsqrtn2 right)$非対称関数の直和に基づくクラスに対して、最適な正確な量子クエリアルゴリズム(Q_algo(f)$)を得る。 Q_algo$のクエリ複雑性は$lceil frac3n4 rceil$であるのに対して、$D_oplus(f)$は$n-1$と$lceil frac3n4 rceの間で異なる。
  論文  参考訳（メタデータ） (2020-08-14T12:17:48Z)

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

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