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

The group testing problem consists of determining a small set of defectiveitems from a larger set of items based on tests on groups of items, and isrelevant in applications such as medical testing, communication protocols,pattern matching, and many more. While rigorous group testing algorithms havelong been known with runtime at least linear in the number of items, a recentline of works has sought to reduce the runtime to ${\rm poly}(k \log n)$, where$n$ is the number of items and $k$ is the number of defectives. In this paper,we present such an algorithm for non-adaptive probabilistic group testingtermed {\em bit mixing coding} (BMC), which builds on techniques that encodeitem indices in the test matrix, while incorporating novel ideas based onerasure-correction coding. We show that BMC achieves asymptotically vanishingerror probability with $O(k \log n)$ tests and $O(k^2 \cdot \log k \cdot \logn)$ runtime, in the limit as $n \to \infty$ (with $k$ having an arbitrarydependence on $n$). This closes a recently-proposed open problem ofsimultaneously achieving ${\rm poly}(k \log n)$ decoding time using $O(k \logn)$ tests without any assumptions on $k$. In addition, we show that the samescaling laws can be attained in a commonly-considered noisy setting, in whicheach test outcome is flipped with constant probability.

Sublinear-Time Non-Adaptive Group Testing with $O(k \log n)$ Tests via Bit-Mixing Coding