AI & ML
Improved Constants in the Kautz-Singleton Construction for Probabilistic Group Testing
arXiv stat.TH0 views
arXiv:2611.25468v1 Announce Type: cross Abstract: We consider the probabilistic nonadaptive group testing problem, in which a uniformly random defective set of size $d$ is to be identified among $N$ items using a binary test matrix. For the explicit Kautz--Singleton construction, it is known that order-optimal scaling $T=\Theta(d\log N)$ for high-probability recovery can be achieved in the regime $d=\Omega(\log^2 N)$. However, the leading constant in this scaling remains uncharacterized even for standard low-complexity decoders. In this work, we revisit the probabilistic analysis of this construction and improve the leading constant for the COMP decoder, as well as establishing the same bound for the DD decoder. Our approach relies on a sharper analysis of the number of distinct roots associated with the defective items, yielding tighter bounds on the decoding error probability. In particular, we show that both COMP and DD achieve vanishing average error probability with $T\le (1/\ln 2+\varepsilon)d\log N$ tests for any $\varepsilon>0$, in the admissible regime $N=q^k$ for some prime power $q = \Theta(d)$ and integer $k \ge 2$. For COMP, this leading constant matches that of the random near-constant column weight design, whereas for DD, a gap remains except in the sparse regime $d = N^{o(1)}$.
Source:https://arxiv.org/abs/2611.25468PreviousFaithful Generative Modeling for Censored Time-to-Event Data: From Distributional Fidelity to Statistical InferenceNextDifferentially Private Score Estimation with Applications to Score-Based Generative Models
Related posts
VESTA: Visual Exploration with Statistical Tool Agents
0arXiv stat.CO
An interpretable semiparametric Bayesian machine learning model for high-dimensional circulating epigenetic signatures of multiple myeloma
0arXiv stat.CO
Quantum Nondecimated Wavelet Transform: Theory, Circuits, and Applications
0arXiv stat.CO
dapper: Data Augmentation for Private Posterior Estimation in R
0arXiv stat.CO
HAVAPlot: A Web-Based Scientific Visualization and Post-Processing Platform
0arXiv stat.CO
ISC Stormcast For Friday, November 20th, 2026 https://isc.sans.edu/podcastdetail/10188, (Fri, Nov 20th)
0SANS ISC