論文の概要: A Version Space Approach for Digital Circuit Analysis

• arxiv url: http://arxiv.org/abs/2609.00609v1
• Date: Tue, 01 Sep 2026 02:49:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-02 16:31:36.246427
• Title: A Version Space Approach for Digital Circuit Analysis
• Title（参考訳）: ディジタル回路解析のためのバージョン空間アプローチ
• Authors: Mitchell A. Thornton,
• Abstract要約: 本稿では、バージョン空間ビューを一つの手法として開発し、2つの回路解析問題に適用する。 1つ目は確率的組合せ同値チェックで、候補はブール関数であり、観測は修正ハールスペクトル係数である。 第2のアプリケーションは、論理ロックされたネットリストのキーカウントであり、候補がキー、観察がオラクルの応答である。
• 参考スコア（独自算出の注目度）: 1.3537117504260623
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many questions about a digital circuit take the same form. A hidden object is consistent with a set of observations, and one wants to know how many remain consistent and which observation to make next. The set of surviving candidates is the version space, and its size, on a logarithmic scale, measures how much the observations have settled. This paper develops the version-space view as one method and applies it to two circuit-analysis problems usually treated as unrelated. The first is probabilistic combinational equivalence checking, where the candidates are Boolean functions and the observations are modified-Haar spectral coefficients. A method proposed in 2002 posed this counting problem and solved only two special cases, leaving the general case an enumeration exponential in the number of observations. We close it. A reparameterization onto block sums turns the dependence among nested coefficients into locality, a sum--product recursion counts the surviving functions exactly in time polynomial in the truth-table size, closed forms follow for a single coefficient, a coefficient pair, and every ancestor-closed set, and the error of the independence approximation the 2002 work resorted to equals a computable lattice index. Every formula is checked against exhaustive enumeration and reproduces the 2002 tables. The second application is key counting for logic-locked netlists, where the candidates are keys and the observations are oracle responses. The same recursion, run over the gate-level factor graph, computes the number of keys still consistent with a set of queries; across seventy instances of the TrustHub obfuscation release the surviving entropy falls below the advertised key length every time. The two applications are one method: a witness supplies observations, each removes candidates, and the version space is counted exactly.
• Abstract（参考訳）: デジタル回路に関する多くの疑問は同じ形を取る。 隠れた物体は一連の観測と一致しており、何人が一貫性を持ち、次にどの観測を行うべきかを知りたがっている。 生き残った候補の集合はバージョン空間であり、その大きさは対数スケールで、観測がどれだけ落ち着いたかを測定する。 本稿では、バージョン空間ビューを1つの手法として開発し、2つの回路解析問題に適用する。 1つ目は確率的組合せ同値チェックで、候補はブール関数であり、観測は修正ハールスペクトル係数である。 2002年に提案された手法は、この計数問題を提起し、2つの特別なケースだけを解決し、一般的なケースは観測数で指数関数的に列挙される。 私たちはそれを閉じます。 ブロック和に対する再パラメータ化は、ネスト係数間の依存を局所性に変換し、和積再帰は真理テーブルサイズの時間多項式における残余関数を正確にカウントし、閉形式は単一の係数、係数対、すべての祖先閉集合を従え、2002年の独立近似の誤差は計算可能な格子指数に等しい。 全ての公式は全列挙に対してチェックされ、2002年の表を再現する。 第2のアプリケーションは、論理ロックされたネットリストのキーカウントであり、候補がキー、観察がオラクルの応答である。 同じ再帰はゲートレベルの因子グラフ上で実行され、クエリのセットとまだ一致していないキー数を計算する。TrustHubの難読化リリースの70のインスタンスにおいて、生き残ったエントロピーは、毎回宣伝されたキー長以下になる。 目撃者が観察結果を提供し、それぞれ候補を取り除き、バージョン空間を正確にカウントする。

関連論文リスト

• A Compositional Theory of Causally Masked Transformers [50.88598486616582]
  モデルが実装した力学から直接表現性を導出する形式化を開発する。 各アテンションヘッドは、レイヤ内で独立して自身の状態を更新する。 修正されたソフトアテンションは、不可逆なチェックリストのような状態をサポートする。
  論文  参考訳（メタデータ） (2026-07-29T14:47:19Z)
• Evolutional Math: Cross-Validated Island-Model Genetic Programming for Interpretable Symbolic Regression on Small, Wide Datasets [0.0]
  遺伝的プログラミングによるシンボリック回帰は、小さくて広いデータセットで日常的に失敗する。 提案するEvolutional Mathは,4つの設計選択を組み合わせて,コンパクトで解釈可能な式を生成する,オープンソースの遺伝的プログラミングシステムである。
  論文  参考訳（メタデータ） (2026-06-20T10:31:14Z)
• Finite-Sample Inference for Sparsely Permuted Linear Regression [6.2000582635449994]
  我々は、置換係数と回帰係数に関する一般的な統計的推論フレームワークを開発する。 計算目的のために、時間で計算可能な線形代入問題を開発し、高い確率で計算コストの高い従来の最小二乗の解と等価であることを示す。
  論文  参考訳（メタデータ） (2026-01-21T11:00:47Z)
• Recursive random binning to detect and display pairwise dependence [0.0]
  理論と実証的な研究はいくつかの近似を動機付けており、例えば、実価値はあるが直観的な自由度を持つ単純な$chi2$近似である。 異なる近似を持つ再帰的ランダムなビンニングは、様々な非ヌル依存パターンに関する最近のグリッドベースの手法と比較される。 これらの近似を持つ手法は、よく校正され、一般的なテスト代替品に対して比較的強力である。
  論文  参考訳（メタデータ） (2023-11-14T21:43:56Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
  確率感性決定図は、解離ゲートの入力が確率値によってアノテートされる論理回路である。 我々は、局所確率を質量関数のクレーダル集合に置き換えることができる確率の一般化である、クレーダル感性決定図を開発する。 まず,ノイズの多い7セグメント表示画像に基づく簡単なアプリケーションについて検討する。
  論文  参考訳（メタデータ） (2020-08-19T16:04:34Z)
• Fused-Lasso Regularized Cholesky Factors of Large Nonstationary Covariance Matrices of Longitudinal Data [0.0]
  大きな共分散行列のコレスキー因子のサブ対角線の滑らかさは、時系列および長手データに対する自己回帰モデルの非定常度の度合いと密接に関連している。 行ごとに分離するColesky因子のスパース推定アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-22T02:38:16Z)
• A Robust Functional EM Algorithm for Incomplete Panel Count Data [66.07942227228014]
  完全無作為な仮定(MCAR)の下での数え上げ過程の平均関数を推定する機能的EMアルゴリズムを提案する。 提案アルゴリズムは、いくつかの一般的なパネル数推定手法をラップし、不完全数にシームレスに対処し、ポアソン過程の仮定の誤特定に頑健である。 本稿では, 数値実験による提案アルゴリズムの有用性と喫煙停止データの解析について述べる。
  論文  参考訳（メタデータ） (2020-03-02T20:04:38Z)
• Consistency of a Recurrent Language Model With Respect to Incomplete Decoding [67.54760086239514]
  逐次言語モデルから無限長のシーケンスを受信する問題について検討する。 不整合に対処する2つの対策として、トップkと核サンプリングの一貫性のある変種と、自己終端の繰り返し言語モデルを提案する。
  論文  参考訳（メタデータ） (2020-02-06T19:56:15Z)

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

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