論文の概要: 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年のベンチマークによるアルゴリズムの包括的実験的評価は、スパースハッシュ関数の使用が大幅な高速化につながることを証明している。

関連論文リスト

• A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions [0.0]
  我々は,暗号アルゴリズムに焦点をあてて,準拘束的二項最適化の最先端を推し進めることを目指している。 AES-128/192/256、MD5、SHA1、SHA256など、最も広く使われている暗号アルゴリズムについて考察する。 これらの結果から,QUBO 行列のスパースと係数の大きさを低く保ちながら,これまでに公表した結果と比較して,QUBO のインスタンスを数千の論理変数で減らした。
  論文  参考訳（メタデータ） (2024-09-10T18:46:26Z)
• 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)
• Scalable network reconstruction in subquadratic time [0.0]
  本稿では,この2次ベースラインを大幅に上回る広範囲の再構成問題に適用可能な一般アルゴリズムを提案する。 我々のアルゴリズムは、高い確率で最適なエッジ候補を生成する第2の隣人探索に依存している。 本アルゴリズムは2次ベースラインよりも桁違いに高速な性能を実現する。
  論文  参考訳（メタデータ） (2024-01-02T19:00:13Z)
• 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)
• 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)

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

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