論文の概要: Sparse Hashing for Scalable Approximate Model Counting: Theory and
Practice
- arxiv url: http://arxiv.org/abs/2004.14692v1
- Date: Thu, 30 Apr 2020 11:17:26 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-08 05:45:11.711117
- Title: Sparse Hashing for Scalable Approximate Model Counting: Theory and
Practice
- Title(参考訳): スケーラブルな近似モデルカウントのためのスパースハッシュ:理論と実践
- Authors: Kuldeep S. Meel and S. Akshay
- Abstract要約: n 変数上の CNF 式 F が与えられたとき、モデルカウントや #SAT の問題は F の満足な割り当ての数を計算することである。
近年,効率的なアルゴリズム技術開発への取り組みが急増している。
- 参考スコア(独自算出の注目度): 36.8421113576893
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a CNF formula F on n variables, the problem of model counting or #SAT
is to compute the number of satisfying assignments of F . Model counting is a
fundamental but hard problem in computer science with varied applications.
Recent years have witnessed a surge of effort towards developing efficient
algorithmic techniques that combine the classical 2-universal hashing with the
remarkable progress in SAT solving over the past decade. These techniques
augment the CNF formula F with random XOR constraints and invoke an NP oracle
repeatedly on the resultant CNF-XOR formulas. In practice, calls to the NP
oracle calls are replaced a SAT solver whose runtime performance is adversely
affected by size of XOR constraints. The standard construction of 2-universal
hash functions chooses every variable with probability p = 1/2 leading to XOR
constraints of size n/2 in expectation. Consequently, the challenge is to
design sparse hash functions where variables can be chosen with smaller
probability and lead to smaller sized XOR constraints.
In this paper, we address this challenge from theoretical and practical
perspectives. First, we formalize a relaxation of universal hashing, called
concentrated hashing and establish a novel and beautiful connection between
concentration measures of these hash functions and isoperimetric inequalities
on boolean hypercubes. This allows us to obtain (log m) tight bounds on
variance and dispersion index and show that p = O( log(m)/m ) suffices for
design of sparse hash functions from {0, 1}^n to {0, 1}^m. We then use sparse
hash functions belonging to this concentrated hash family to develop new
approximate counting algorithms. A comprehensive experimental evaluation of our
algorithm on 1893 benchmarks demonstrates that usage of sparse hash functions
can lead to significant speedups.
- Abstract(参考訳): n 変数上の CNF 式 F が与えられたとき、モデルカウントや #SAT の問題は F の満足な割り当ての数を計算することである。
モデルカウント(英: Model counting)は、様々な応用を持つコンピュータ科学における基本的な問題である。
近年、従来の2ユニバーサルハッシュ法と過去10年間のsat解の著しい進歩を組み合わせた効率的なアルゴリズム手法の開発への取り組みが急増している。
これらの手法は、ランダムなXOR制約でCNF式Fを増大させ、結果のCNF-XOR式でNPオラクルを繰り返し呼び出す。
実際には、np oracleコールの呼び出しは、xor制約のサイズによってランタイムパフォーマンスが悪影響を受けるsatソルバに置き換えられる。
2ユニバーサルハッシュ関数の標準的な構成は、予想される大きさ n/2 の XOR 制約につながる確率 p = 1/2 のすべての変数を選択する。
したがって、より小さな確率で変数を選択でき、より小さなXOR制約を導出できるスパースハッシュ関数を設計することが課題である。
本稿では,この課題を理論的および実用的観点から解決する。
まず、集中ハッシュと呼ばれる普遍ハッシュの緩和を定式化し、これらのハッシュ関数の集中度とブール超キューブの等尺不等式の間の、新しくて美しい接続を確立する。
これにより分散と分散指数の(log m)密接な境界を得ることができ、p = o( log(m)/m ) が {0, 1}^n から {0, 1}^m へのスパースハッシュ関数の設計に十分であることを示せる。
次に、この集中ハッシュファミリーに属するスパースハッシュ関数を用いて、新しい近似カウントアルゴリズムを開発する。
1893年のベンチマークによるアルゴリズムの包括的実験的評価は、スパースハッシュ関数の使用が大幅な高速化につながることを証明している。
関連論文リスト
- Calculating the expected value function of a two-stage stochastic
optimization program with a quantum algorithm [0.0]
2段階の最適化では、将来の決定の期待されるコストを計算し、現在の最良の決定を知らせる。
本研究では,2段階最適化問題における期待値関数を,確率変数の複雑性から大きく独立して推定する量子アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-02-23T00:07:34Z) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳(メタデータ) (2023-12-18T18:29:01Z) - Quantum Sparse Coding [5.130440339897477]
我々はスパース符号化のための量子インスピレーション付きアルゴリズムを開発した。
量子コンピュータとイジングマシンの出現は、より正確な推定につながる可能性がある。
我々はLightrの量子インスパイアされたデジタルプラットフォーム上でシミュレーションデータを用いて数値実験を行う。
論文 参考訳(メタデータ) (2022-09-08T13:00:30Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳(メタデータ) (2022-06-30T03:15:23Z) - Quantum Topological Data Analysis with Linear Depth and Exponential
Speedup [9.820545418277305]
我々はQTDAアルゴリズムを完全にオーバーホールし、$O(n4/(epsilon2 delta))の指数的高速化深度を改良した。
理論的誤差解析とベッチ数推定のための回路・計算時間・深度複雑度について述べる。
論文 参考訳(メタデータ) (2021-08-05T18:56:17Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳(メタデータ) (2020-12-04T15:36:29Z) - Berrut Approximated Coded Computing: Straggler Resistance Beyond
Polynomial Computing [34.69732430310801]
本稿では,ストラグラー効果に対処する代替手法として,Berrut Approximated Coded Computing (BACC)を提案する。
BACCは計算複雑性が低い数値的に安定であることが証明されている。
特に、BACCは、サーバのクラスタ上でディープニューラルネットワークをトレーニングするために使用される。
論文 参考訳(メタデータ) (2020-09-17T14:23:38Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳(メタデータ) (2020-05-09T02:48:23Z) - Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved
Complexities [21.13934071954103]
本稿では,非インワンテキスト変数 Descent に対する決定論的アルゴリズムを提案する。
SGC仮定の下では,アルゴリズムの複雑さが既存のアルゴリズムの複雑さと一致していることが示される。
結果はオラクル・テキストZO-GDMSAで示され、数値実験により理論的結果が裏付けられる。
論文 参考訳(メタデータ) (2020-01-22T00:05:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。