論文の概要: Auditable Algorithms for Approximate Model Counting
- arxiv url: http://arxiv.org/abs/2312.12362v1
- Date: Tue, 19 Dec 2023 17:47:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-20 14:40:39.313227
- Title: Auditable Algorithms for Approximate Model Counting
- Title（参考訳）: 近似モデルカウントのための可聴性アルゴリズム
- Authors: Kuldeep S. Meel, Supratik Chakraborty, S. Akshay
- Abstract要約: 我々は、$Sigma3P$ oracleを呼び出す新しい決定論的近似カウントアルゴリズムを開発したが、より少ない変数で$SigmaP$ oracleを使用して認証することができる。
これは、監査の複雑さが近似カウントの複雑さのためにどのように交換できるかを初めて示す。
- 参考スコア（独自算出の注目度）: 31.609554468870382
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Model counting, or counting the satisfying assignments of a Boolean formula,
is a fundamental problem with diverse applications. Given #P-hardness of the
problem, developing algorithms for approximate counting is an important
research area. Building on the practical success of SAT-solvers, the focus has
recently shifted from theory to practical implementations of approximate
counting algorithms. This has brought to focus new challenges, such as the
design of auditable approximate counters that not only provide an approximation
of the model count, but also a certificate that a verifier with limited
computational power can use to check if the count is indeed within the promised
bounds of approximation.
Towards generating certificates, we start by examining the best-known
deterministic approximate counting algorithm that uses polynomially many calls
to a $\Sigma_2^P$ oracle. We show that this can be audited via a $\Sigma_2^P$
oracle with the query constructed over $n^2 \log^2 n$ variables, where the
original formula has $n$ variables. Since $n$ is often large, we ask if the
count of variables in the certificate can be reduced -- a crucial question for
potential implementation. We show that this is indeed possible with a tradeoff
in the counting algorithm's complexity. Specifically, we develop new
deterministic approximate counting algorithms that invoke a $\Sigma_3^P$
oracle, but can be certified using a $\Sigma_2^P$ oracle using certificates on
far fewer variables: our final algorithm uses only $n \log n$ variables. Our
study demonstrates that one can simplify auditing significantly if we allow the
counting algorithm to access a slightly more powerful oracle. This shows for
the first time how audit complexity can be traded for complexity of approximate
counting.
- Abstract（参考訳）: モデルカウント、あるいはブール公式の満足する代入を数えることは、多様な応用において根本的な問題である。
この問題の#P硬度を考えると、近似カウントのためのアルゴリズムの開発は重要な研究領域である。
SAT-ソルバの実用的成功に基づいて、最近は理論から近似カウントアルゴリズムの実装へと焦点が移っている。
これにより、モデルカウントの近似を提供するだけでなく、計算能力の制限された検証者が、そのカウントが実際に約束された近似の限界内にあるかどうかをチェックするための証明を提供する監査可能な近似カウンタの設計など、新たな課題に焦点が当てられるようになった。
証明を生成するために、我々は、$\Sigma_2^P$ Oracleへの多項式的に多くの呼び出しを利用する最もよく知られた決定論的近似カウントアルゴリズムを調べることから始める。
元の式が$n$変数を持つ$n^2 \log^2 n$変数上に構築されたクエリで、$\Sigma_2^P$ Oracleで監査可能であることを示す。
n$はしばしば大きいので、証明書内の変数の数を減らせるかどうかを尋ねます -- 潜在的な実装にとって重要な質問です。
これは、カウントアルゴリズムの複雑さのトレードオフによって実現可能であることを示す。
具体的には、$\sigma_3^p$ oracleを呼び出すが、はるかに少ない変数の証明書を使って$\sigma_2^p$ oracleを使って認証することができる、決定論的近似カウントアルゴリズムを開発する。
我々の研究は、カウントアルゴリズムがもう少し強力なオラクルにアクセスできれば、監査を大幅に単純化できることを示した。
これは、監査の複雑さを近似計算の複雑さと交換する初めての方法である。
関連論文リスト
- Accelerated quantum search using partial oracles and Grover's algorithm [0.0]
グロバーのアルゴリズム(英: Grover's algorithm)は、順序のないデータベースを探索する手段として考案されたアルゴリズムであり、量子計算によって生成される結果集合から解を抽出するためにも用いられる。
マッチング条件の各ビットに個別のオラクルを関連付け、独立にテスト可能な複数の部分的なオラクル関数を得るという考え方を探求する。
アルゴリズムは最も単純な検索シナリオに対して検証され、入力されたインデックスビットは置換演算を用いてスクランブルされる。
論文 参考訳（メタデータ） (2024-03-19T11:32:02Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Robust Approximation Algorithms for Non-monotone $k$-Submodular
Maximization under a Knapsack Constraint [0.0]
2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。
提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
論文 参考訳（メタデータ） (2023-09-21T12:42:52Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Efficient Quantum State Synthesis with One Query [0.0]
本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。
我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
論文 参考訳（メタデータ） (2023-06-02T17:49:35Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文 参考訳（メタデータ） (2022-11-28T08:40:12Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Topological obstructions to quantum computation with unitary oracles [0.0]
いくつかのタスクは量子回路では不可能であるが、古典的なバージョンはクローン化などが容易である。
プロセストモグラフィ、オラクル中立化、$sqrt[dim U]U$、$UT$、$Udagger$アルゴリズムの制限を示す。
その結果、線形光学の利点を強化し、緩和因果性の実験に挑戦し、多くのアウトカム測定で新しいアルゴリズムを動機づけた。
論文 参考訳（メタデータ） (2020-11-19T18:52:38Z) - Quantum Approximate Counting with Nonadaptive Grover Iterations [1.14219428942199]
量子設定では、近似カウントは$Oleft(sqrtN/epsilon, sqrtN/K/epsilonright)$クエリで行うことができる。
我々は,非適応的なGrover反復のみを用いるアルゴリズムが$Oleft(sqrtN/epsilonright)$クエリ複雑性を達成可能であることを示す。
論文 参考訳（メタデータ） (2020-10-09T04:48:14Z) - The Sparse Vector Technique, Revisited [67.57692396665915]
我々は、微分プライバシーの文献において最も基礎的で広く適用可能なテクニックの1つを再考する。
この単純なアルゴリズムは、データベース上のあるクエリの値が、私たちが期待している値に近いかどうかをプライベートにテストします。
一つの個人が過剰なクエリの回答に寄与しない限り、クエリのテストを継続できる代替の、等しくシンプルなアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-02T10:50:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。