論文の概要: Auditing Combinatorial Randomness from Finite Transcripts
- arxiv url: http://arxiv.org/abs/2606.22034v1
- Date: Sat, 20 Jun 2026 13:17:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-25 23:10:48.208561
- Title: Auditing Combinatorial Randomness from Finite Transcripts
- Title（参考訳）: 有限文字からの組合せランダム性の検討
- Authors: Faruk Alpay, Levent Sarioglu,
- Abstract要約: 我々は、$m$ラベルから$k$-subsetのブラックボックス監査を、正確にuniform-with-out-replacement nullの下で研究する。
構造的欠陥に対しては, 境界型チ二乗, ペア最大値, シリアルオーバーラップ, アンカードボックスパルション, 低次元差分を用いて, ハイパープレックス上でのNull-Agnostic auditsを構築する。
観測および基準ソース監査全体において、偽発見訂正後の統計は有意なものではない。
- 参考スコア（独自算出の注目度）: 0.2864713389096699
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Public randomness is a security primitive whose deployed behavior is often observable only through a finite transcript. We study black-box auditing of $k$-subset draws from $m$ labels under the exact uniform-without-replacement null. The outcome space has size $\binom{m}{k}$, and unrestricted uniformity testing therefore requires $Θ(\sqrt{\binom{m}{k}}/\varepsilon^2)$ samples, establishing an information-theoretic limit on transcript-only certification. For structured faults, we construct generator-agnostic audits on the hypersimplex using marginal chi-square, pair maxima, serial overlap, anchored-box discrepancy, and low-dimensional $H_0$/MST geometry, all calibrated under the exact combinatorial null. We also prove a finite-witness guarantee whose sample complexity depends logarithmically on the number of audited witnesses rather than on the full support size. Across observed and reference-source audits, no statistic remains significant after false-discovery correction (minimum BH $q=0.279$). GPU Monte Carlo experiments, using up to 300,000 null and 60,000 alternative replications per condition, show that marginal-preserving deviations can evade one-dimensional tests while remaining detectable through joint geometry. At $n=1{,}956$, a block-cluster alternative of strength 0.04 yields power 0.638 for pair maxima versus 0.051 for marginal chi-square; a band-repulsion alternative of strength 0.08 yields power 0.741 for anchored boxes versus 0.051. These results characterize which structured deviations finite public transcripts can detect and the sample sizes required for doing so.
- Abstract（参考訳）: 公開ランダム性(Public randomness)はセキュリティプリミティブであり、デプロイされた振る舞いは有限の転写によってのみ観察可能である。
我々は、$m$ラベルから$k$-subsetのブラックボックス監査を、正確にuniform-with-out-replacement nullの下で研究する。
結果空間のサイズは$\binom{m}{k}$であり、従って制限のない一様性テストは、(\sqrt{\binom{m}{k}}/\varepsilon^2)$サンプルを必要とする。
構造的欠陥に対しては,極小のチ二乗,ペアの最大値,シリアルオーバーラップ,アンカーボックスの誤差,低次元の$H_0$/MST幾何を用いて,超複素数に対するジェネレータ非依存監査を構築した。
また、サンプルの複雑さは、完全なサポートサイズではなく、監査された目撃者の数に対数的に依存する有限知性保証も証明する。
観測および基準ソース監査全体において、偽発見訂正後の統計は有意なものではない(最小BH$q=0.279$)。
GPU Monte Carloの実験では、最大30万のnullと6万の代替レプリケーションを使用して、境界保存偏差が1次元のテストを避けつつ、関節幾何学を通して検出できることが示されている。
n=1{,}956$ で、強度 0.04 のブロッククラスター代替品は、対極値が 0.638 の電力を、辺りが 0.051 の電力を出力し、強度 0.08 のバンド反発代替品は、アンカーボックスが 0.741 の電力を 0.051 に対して出力する。
これらの結果は、有限公文書が検出できる構造的偏差とそれに必要なサンプルサイズを特徴付ける。
関連論文リスト
- Is Spurious Correlation Removal Always Learnable? [56.28155520961125]
不変学習は、構造が統計的に識別可能であっても失敗することがある。
ブラックボックスサンプリング可能な教師付きスパースリカバリプリミティブの下では、実証可能な多次元環境が存在する。
合成および実際のデータセットは、予測されたギャップと遷移を示し、単純な多様性診断を動機付ける。
論文 参考訳（メタデータ） (2026-06-11T05:49:43Z) - BOKBO (Best of K Bad Options): Calibrated Abstention for VLA Policies [1.3918848543076061]
VLA(Vision-suite-action)ポリシー、RoboMonkey、SEAL、MG-Select、V-GPSなどのメソッドに対するテストタイムスケーリングは、推論時にK候補アクションチャンクをサンプリングし、検証-ベストを実行する。
K-sample VLA推論のための最初の共形吸収層であるBOKBOを提案する。
論文 参考訳（メタデータ） (2026-05-28T23:39:09Z) - Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。
これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
論文 参考訳（メタデータ） (2026-05-22T15:05:33Z) - Adaptive Confidence Intervals in Efron's Gaussian Two-Groups Model [28.636700996382558]
敵のノイズに満ちた性質により、Efronのガウス的二群分数モデルにおいて、ヌル位置パラメータ$$に対する信頼区間を研究する。
信頼区間の最小最適長を、未知の割合の汚染と全てのノイズに満ちた敵に対して、所定のカバレッジレベルで特徴付ける。
論文 参考訳（メタデータ） (2026-04-28T22:40:54Z) - Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements [66.94250413799232]
分散パラメータ-サーバ-ワーカー設定における乱数ベクトル$X$の推定について検討する。
主な課題は、敵の計測と非同期である。
その結果, 分散線形推定におけるロバスト性, 識別性, 統計的効率の統一的有限時間評価が得られた。
論文 参考訳（メタデータ） (2026-04-07T11:45:55Z) - Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。
クラスタリングの精度に対する望ましい信頼性を達成するのに必要なクエリ数の基本的下位境界を確立する。
我々は、一般化された同値比統計の計算可能な変種を開発し、その下限に対する性能ギャップを正確に推定できることを実証的に示す。
論文 参考訳（メタデータ） (2026-02-05T14:16:47Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Sharp Constants in Uniformity Testing via the Huber Statistic [16.384142529375435]
一様性テスト(英: Uniformity testing)は、プロパティテストにおいて最もよく研究されている問題の1つである。
1-デルタ確率を持つ任意の$epsilon$-far分布と$m$要素上の均一分布を区別する最適なサンプル複雑性は$nであることが知られている。
衝突試験機は, 均一入力と非一様入力の分離の標準偏差数において, 急激な最大定数を達成することを示す。
論文 参考訳（メタデータ） (2022-06-21T20:43:53Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。