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
Hydra · Coeziune OM–IA — the complete DOI registry (2026-11-20): 8 published works
0dev.to OpenSource
Stop Renting Cloud GPUs & VPS: 4 Legitimate Free Compute Tiers in 2026 (Plus Billing Pitfalls)
0dev.to OpenSource
How to Decode a Wall of Wingdings Without a Key
0dev.to Programming
Beyond the Hype: How Modern Businesses Can Actually Benefit from AI Today
0dev.to Programming
How to Free Up Space on Android Without Deleting Anything
0dev.to Programming

All my git repos in one file: manage them day to day, rebuild them on a new machine
0dev.to Git