Auditing Combinatorial Randomness from Finite Transcripts

• URL: http://arxiv.org/abs/2606.22034v1
• Date: Sat, 20 Jun 2026 13:17:44 GMT
• Title: Auditing Combinatorial Randomness from Finite Transcripts
• Abstract summary: We study black-box auditing of $k$-subset draws from $m$ labels under the exact uniform-without-replacement null.<n>For structured faults, we construct generator null-agnostic audits on the hypersimplex using marginal chi-square, pair maxima, serial overlap, anchored-boxpulsion and low-dimensional discrepancy.<n>Across observed and reference-source audits, no statistic remains significant after false-discovery correction.
• Score: 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.

Related papers

• Observational Indistinguishability and Integrity Blind Regions in Hybrid Quantum-Classical Workflows [0.0]
  We present a claim-relative evidence/reference framework for hybrid quantum-classical workflow integrity.<n> Observational indistinguishability yields structural blind regions, distinct from finite-batch statistical misses.
  arXiv  Detail & Related papers  (2026-09-15T13:16:37Z)
• The geometry of AI validation: Exact certification limits for iid best-of-N search [0.0]
  We represent validation and deployment rules as kernels over a reliability surface.<n>Knowing best-of-$n$ reliability through $n=m$ leaves exact ambiguity width $B_m,N=1+2sum_r=1m(-1)rcos2Nr/[(m+1)]$.
  arXiv  Detail & Related papers  (2026-08-21T15:18:11Z)
• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
  arXiv  Detail & Related papers  (2026-08-06T19:49:48Z)
• Information-theoretic limits on undetectable parameter-estimation attacks in continuous-variable quantum key distribution [1.7205106391379026]
  We formalize a certificate-forgery hypothesis test and identify its detectability with an information-theoretic rate.<n>Relative to a set $mathcalM$ of trusted observables, the forgery- detectability rate $g_mathcal M$ of a benign-statistics certificate is the missed-detection Stein exponent.
  arXiv  Detail & Related papers  (2026-07-25T23:36:36Z)
• Is Spurious Correlation Removal Always Learnable? [56.28155520961125]
  Invariant learning can fail even when the structure is statistically identifiable.<n>We show a conditional computational barrier: under a black-box samplable supervised sparse recovery primitive, there exist emphamplable multi-dimensional environments.<n>Synthetic and real datasets illustrate the predicted gaps and transitions and motivate simple diversity diagnostics.
  arXiv  Detail & Related papers  (2026-06-11T05:49:43Z)
• BOKBO (Best of K Bad Options): Calibrated Abstention for VLA Policies [1.3918848543076061]
  Test-time scaling for vision-suite-action (VLA) policies, methods such as RoboMonkey, SEAL, MG-Select, and V-GPS, samples K candidate action chunks at inference and executes the verifier-best.<n>We propose BOKBO, the first conformal abstention layer for K-sample VLA inference, providing finite-sample distribution-free guarantees on executed-violation rate.
  arXiv  Detail & Related papers  (2026-05-28T23:39:09Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• Adaptive Confidence Intervals in Efron's Gaussian Two-Groups Model [28.636700996382558]
  Motivated by noise-oblivious nature of adversaries, we study confidence intervals for the null location parameter $$ in Efron's Gaussian two-groups fraction model.<n>We characterize the minimax-optimal length among confidence intervals with a prescribed coverage level uniformly over the unknown proportion contamination and all noise-oblivious adversaries.
  arXiv  Detail & Related papers  (2026-04-28T22:40:54Z)
• Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements [66.94250413799232]
  We study mean estimation of a random vector $X$ in a distributed parameter-server-worker setup.<n>Key challenges are adversarial measurements and asynchrony.<n>Results provide a unified finite-time characterization of robustness, identifiability, and statistical efficiency in distributed linear estimation with adversarial workers.
  arXiv  Detail & Related papers  (2026-04-07T11:45:55Z)
• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  We propose a new analysis framework for clustering $M$ items into an unknown number of $K$ distinct groups using noisy and actively collected responses.<n>We establish a fundamental lower bound on the expected number of queries needed to achieve a desired confidence in the accuracy of the clustering.<n>We develop a computationally feasible variant of the Generalized Likelihood Ratio statistic and show that its performance gap to the lower bound can be accurately empirically estimated.
  arXiv  Detail & Related papers  (2026-02-05T14:16:47Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  We study contextual bandits with probabilistically triggered arms (C$2$MAB-T) under a variety of smoothness conditions. Under the triggering modulated (TPM) condition, we devise the C$2$-UC-T algorithm and derive a regret bound $tildeO(dsqrtT)$.
  arXiv  Detail & Related papers  (2023-03-30T02:51:00Z)
• Sharp Constants in Uniformity Testing via the Huber Statistic [16.384142529375435]
  Uniformity testing is one of the most well-studied problems in property testing. It is known that the optimal sample complexity to distinguish the uniform distribution on $m$ elements from any $epsilon$-far distribution with $1-delta probability is $n. We show that the collisions tester achieves a sharp maximal constant in the number of standard deviations of separation between uniform and non-uniform inputs.
  arXiv  Detail & Related papers  (2022-06-21T20:43:53Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  We are given i.i.d. samples from a distribution of the form $Z = (1-epsilon) X + epsilon B$, where $X$ is a zero-mean and unknown covariance Gaussian $mathcalN(0, Sigma)$. In the absence of contamination, prior work gave a simple tester for this hypothesis testing task that uses $O(d)$ samples. We prove a sample complexity lower bound of $Omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma
  arXiv  Detail & Related papers  (2020-12-31T18:24:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.