English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Recent advances in noiseless non-adaptive group testing have led to a preciseasymptotic characterization of the number of tests required forhigh-probability recovery in the sublinear regime $k = n^{\theta}$ (with$\theta \in (0,1)$), with $n$ individuals among which $k$ are infected.However, the required number of tests may increase substantially underreal-world practical constraints, notably including bounds on the maximumnumber $\Delta$ of tests an individual can be placed in, or the maximum number$\Gamma$ of individuals in a given test. While previous works have givenrecovery guarantees for these settings, significant gaps remain between theachievability and converse bounds. In this paper, we substantially orcompletely close several of the most prominent gaps. In the case of$\Delta$-divisible items, we show that the definite defectives (DD) algorithmcoupled with a random regular design is asymptotically optimal in dense scalingregimes, and optimal to within a factor of $\eul$ more generally; we establishthis by strengthening both the best known achievability and converse bounds. Inthe case of $\Gamma$-sized tests, we provide a comprehensive analysis of theregime $\Gamma = \Theta(1)$, and again establish a precise threshold provingthe asymptotic optimality of SCOMP (a slight refinement of DD) equipped with atailored pooling scheme. Finally, for each of these two settings, we providenear-optimal adaptive algorithms based on sequential splitting, and provablydemonstrate gaps between the performance of optimal adaptive and non-adaptivealgorithms.

Near optimal sparsity-constrained group testing: improved bounds and algorithms