Fugu-MT 論文翻訳(概要): Efficient Parallel Algorithm for Decomposing Hard CircuitSAT Instances

論文の概要: Efficient Parallel Algorithm for Decomposing Hard CircuitSAT Instances

arxiv url: http://arxiv.org/abs/2602.17130v1
Date: Thu, 19 Feb 2026 07:05:48 GMT
ステータス: 翻訳完了
システム内更新日: 2026-02-20 15:21:28.799481
Title: Efficient Parallel Algorithm for Decomposing Hard CircuitSAT Instances
Title（参考訳）: ハードサーキットSATインスタンスを分解する効率的な並列アルゴリズム
Authors: Victor Kondratiev, Irina Gribanova, Alexander Semenov,
Abstract要約: ハードサーキットSATインスタンスを分解する新しい並列アルゴリズムを提案する。本手法はパラメータ化並列アルゴリズムとして実装され,パラメータの調整により高品質な分解を効率的に同定できる。
参考スコア（独自算出の注目度）: 44.0167033148715
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We propose a novel parallel algorithm for decomposing hard CircuitSAT instances. The technique employs specialized constraints to partition an original SAT instance into a family of weakened formulas. Our approach is implemented as a parameterized parallel algorithm, where adjusting the parameters allows efficient identification of high-quality decompositions, guided by hardness estimations computed in parallel. We demonstrate the algorithm's practical efficacy on challenging CircuitSAT instances, including those encoding Logical Equivalence Checking of Boolean circuits and preimage attacks on cryptographic hash functions.
Abstract（参考訳）: ハードサーキットSATインスタンスを分解するための新しい並列アルゴリズムを提案する。この手法は、オリジナルのSATインスタンスを弱化された公式の族に分割する特別な制約を用いる。本手法はパラメータ化並列アルゴリズムとして実装され,パラメータの調整により並列に計算された硬さ推定によって導かれる高品質な分解の効率的な同定が可能となる。本稿では,ブール回路の論理等価チェックの符号化や暗号ハッシュ関数の事前攻撃など,CircuitSATインスタンス上でのアルゴリズムの有効性を実証する。

関連論文リスト

Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
周期的な対角構造を持つスパース行列を符号化するための明示的な量子回路を提供する。本手法の様々な応用は, 微分問題を解く文脈で論じる。
論文参考訳（メタデータ） (2026-02-11T07:24:33Z)
Stabilizer circuit verification [0.0]
そこで本研究では,安定化回路の完全特徴化と完全検証を行うための,一組の効率的な古典アルゴリズムを提案する。安定化回路の等価性をチェックするアルゴリズムを提案する。全てのアルゴリズムは、対応する回路表現間の測定結果の関係を提供する。
論文参考訳（メタデータ） (2023-09-15T18:06:17Z)
Massively Parallel Continuous Local Search for Hybrid SAT Solving on GPUs [5.245714076090567]
我々は、勾配駆動連続局所探索に基づく高並列ハイブリッドSATソルバであるFastFourierSATを提案する。以上の結果から,FastFourierSATはCPU上で実装された以前のプロトタイプの100倍以上の速度で勾配を計算することがわかった。 FastFourierSATは、ほとんどのインスタンスを解決し、より大きなインスタンスで有望なパフォーマンスを示す。
論文参考訳（メタデータ） (2023-08-29T04:50:07Z)
Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits [5.847084649531299]
トンプソンサンプリングとグリーディは有望な経験的性能を示したが、これは悲観的な理論的後悔の境界とは対照的である。本稿では,問題パラメータの周辺における不確かさ楕円体の幾何学的特性を追従する新しいデータ駆動手法を提案する。この手法により,Greedy,OFUL,Thompsonサンプルを含む幅広いアルゴリズムに対して,幾何学的情報を含むデータ駆動型頻繁な後悔境界を定式化することができる。
論文参考訳（メタデータ） (2023-06-26T17:38:45Z)
FastDiagP: An Algorithm for Parallelized Direct Diagnosis [64.65251961564606]
FastDiagは、競合を事前に決定せずに診断計算をサポートする典型的な直接診断アルゴリズムである。本稿では,投機的プログラミングのアイデアに基づく新しいアルゴリズムであるFastDiagPを提案する。このメカニズムは、高速な回答で一貫性チェックを提供し、アルゴリズムのランタイムパフォーマンスを高めるのに役立つ。
論文参考訳（メタデータ） (2023-05-11T16:26:23Z)
Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits [58.83758257568434]
LEC インスタンスの SAT 符号化の硬さは SAT パーティショニングでは textitw.r. と推定できることを示す。そこで本研究では, SAT符号化の難易度を精度良く推定できるパーティショニング法を提案する。
論文参考訳（メタデータ） (2022-10-04T09:19:13Z)
Accelerating ERM for data-driven algorithm design using output-sensitive techniques [26.32088674030797]
データ駆動型アルゴリズム設計のための効率的な学習アルゴリズムを開発するための技術について研究する。提案手法は,超平面の集合によって誘導されるポリトープを列挙する出力感受性アルゴリズムである。本稿では、価格問題、リンクベースのクラスタリング、動的プログラミングに基づくシーケンスアライメントのアルゴリズムを提供することにより、我々の技術を説明する。
論文参考訳（メタデータ） (2022-04-07T17:27:18Z)
Temporal Parallelization of Inference in Hidden Markov Models [0.0]
本稿では隠れマルコフモデル(hmms)における推論の並列化アルゴリズムを提案する。パラレル・バックワード型フィルタ・スムージングアルゴリズムとパラレル・ビタビ型max-a-posteriori(MAP)を提案する。高並列処理ユニット(GPU)における提案手法の性能と古典的手法とを実証的に比較する。
論文参考訳（メタデータ） (2021-02-10T21:26:09Z)
Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文参考訳（メタデータ） (2020-07-01T18:43:32Z)
Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文参考訳（メタデータ） (2020-01-29T09:40:58Z)

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