論文の概要: Variables Ordering Optimization in Boolean Characteristic Set Method Using Simulated Annealing and Machine Learning-based Time Prediction

• arxiv url: http://arxiv.org/abs/2509.14754v1
• Date: Thu, 18 Sep 2025 09:02:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-19 17:26:53.136344
• Title: Variables Ordering Optimization in Boolean Characteristic Set Method Using Simulated Annealing and Machine Learning-based Time Prediction
• Title（参考訳）: 模擬アニーリングと機械学習に基づく時間予測を用いたブール特性集合法における変数順序付け最適化
• Authors: Minzhong Luo, Yudong Sun, Yin Long,
• Abstract要約: 本稿では,機械学習に基づく時間予測とシミュレーションアニーリング(SA)を統合した新しいフレームワークを提案する。 我々は、任意の変数の順序付けに要する問題解決時間を推定するために、正確なML予測器 ft(X) を訓練する。 実験により,本手法は標準BCSアルゴリズムよりもかなり優れていることが示された。
• 参考スコア（独自算出の注目度）: 1.654967376694554
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Solving systems of Boolean equations is a fundamental task in symbolic computation and algebraic cryptanalysis, with wide-ranging applications in cryptography, coding theory, and formal verification. Among existing approaches, the Boolean Characteristic Set (BCS) method[1] has emerged as one of the most efficient algorithms for tackling such problems. However, its performance is highly sensitive to the ordering of variables, with solving times varying drastically under different orderings for fixed variable counts n and equations size m. To address this challenge, this paper introduces a novel optimization framework that synergistically integrates machine learning (ML)-based time prediction with simulated annealing (SA) to efficiently identify high-performance variables orderings. Weconstruct a dataset comprising variable frequency spectrum X and corresponding BCS solving time t for benchmark systems(e.g., n = m = 28). Utilizing this data, we train an accurate ML predictor ft(X) to estimate solving time for any given variables ordering. For each target system, ft serves as the cost function within an SA algorithm, enabling rapid discovery of low-latency orderings that significantly expedite subsequent BCS execution. Extensive experiments demonstrate that our method substantially outperforms the standard BCS algorithm[1], Gr\"obner basis method [2] and SAT solver[3], particularly for larger-scale systems(e.g., n = 32). Furthermore, we derive probabilistic time complexity bounds for the overall algorithm using stochastic process theory, establishing a quantitative relationship between predictor accuracy and expected solving complexity. This work provides both a practical acceleration tool for algebraic cryptanalysis and a theoretical foundation for ML-enhanced combinatorial optimization in symbolic computation.
• Abstract（参考訳）: ブール方程式の解法は記号計算と代数的暗号解析の基本的な課題であり、暗号、符号化理論、形式的検証に広く応用されている。 既存の手法の中では、Boolean Characteristics Set (BCS) 法[1] がそのような問題に対処するための最も効率的なアルゴリズムの1つとして登場した。 しかし、その性能は変数の順序に非常に敏感であり、固定変数数 n と方程式サイズ m の異なる順序の下で解時間が大きく変化する。 この課題に対処するために,機械学習に基づく時間予測と模擬アニーリング(SA)を相乗的に統合し,高性能変数の順序付けを効率的に識別する,新しい最適化フレームワークを提案する。 ベンチマークシステム(例えば、n = m = 28)に対して、可変周波数スペクトルXと対応するBCS問題解決時間tからなるデータセットを構築する。 このデータを用いて、任意の変数の順序付けに要する問題解決時間を推定するために、正確なML予測器 ft(X) を訓練する。 各ターゲットシステムに対して、ftはSAアルゴリズム内のコスト関数として機能し、BCSの実行を著しく高速化する低遅延順序の迅速な発見を可能にする。 特に大規模システム(例えば、n = 32)では、我々の手法が標準BCSアルゴリズム[1], Gr\, SATソルバ[3]を大幅に上回ることを示した。 さらに,確率的プロセス理論を用いてアルゴリズム全体の確率的時間複雑性境界を導出し,予測精度と予測解複雑性の定量的関係を確立する。 この研究は、代数的暗号解析のための実用的な加速ツールと、シンボリック計算におけるML強化組合せ最適化の理論的基礎の両方を提供する。

関連論文リスト

• Federated Conditional Stochastic Optimization [110.513884892319]
  条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。 本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-04T01:47:37Z)
• AxOMaP: Designing FPGA-based Approximate Arithmetic Operators using Mathematical Programming [2.898055875927704]
  FPGAの近似演算子を合成するための,データ解析による数学的プログラミングに基づく手法を提案する。 具体的には、特徴量データの相関解析の結果に基づいて、混合整数の2次制約付きプログラムを定式化する。 従来の進化的アルゴリズムによる最適化と比較して,PPAとBEHAVの併用最適化において,ハイパーボリュームの最大21%の改善が報告されている。
  論文  参考訳（メタデータ） (2023-09-23T18:23:54Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。 所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。 我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
  論文  参考訳（メタデータ） (2023-04-12T14:51:47Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Dual Optimization for Kolmogorov Model Learning Using Enhanced Gradient Descent [8.714458129632158]
  コルモゴロフモデル(コルモゴロフモデル、英: Kolmogorov model、KM)は、確率変数の集合の基本的な確率構造を学ぶための解釈可能で予測可能な表現手法である。 正規化双対最適化と拡張勾配降下法(GD)を併用した計算スケーラブルなKM学習アルゴリズムを提案する。 提案したKM学習アルゴリズムを用いた論理的関係マイニングの精度は80%以上である。
  論文  参考訳（メタデータ） (2021-07-11T10:33:02Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)
• Minimal Cycle Representatives in Persistent Homology using Linear Programming: an Empirical Study with User's Guide [4.46514714749204]
  永続ホモロジークラスのサイクル代表は、データ内のトポロジ的特徴の説明に使用することができる。 この問題を解決するためのアプローチの1つは、データのコンテキストで意味のある尺度に対して代表者の選択を最適化することです。
  論文  参考訳（メタデータ） (2021-05-14T18:38:48Z)
• Parallel Scheduling Self-attention Mechanism: Generalization and Optimization [0.76146285961466]
  本稿では,SAT(Satisfiability check)ソルバによって解決された小インスタンスの最適スケジューリングから導いた一般スケジューリングアルゴリズムを提案する。 余剰計算をスキップする際のさらなる最適化戦略も推進され、元の計算の約25%と50%の削減が達成される。 提案アルゴリズムは、入力ベクトルの数がアーキテクチャで利用可能な演算ユニットの数に割り切れる限り、問題のサイズにかかわらず適用可能である。
  論文  参考訳（メタデータ） (2020-12-02T12:04:16Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)

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

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