Lune

FOCS2020Top-tier venue

Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time

Mahdi Cheraghchi, Vasileios Nakos

Abstract

In the long-studied problem of combinatorial group testing, one is asked to detect a set of k defective items out of a population of size n, using m ≪ n disjunctive measurements. In the non-adaptive setting, the most widely used combinatorial objects are disjunct and listdisjunct matrices, which define incidence matrices of test schemes. Disjunct matrices allow the identification of the exact set of defectives, whereas list disjunct matrices identify a small superset of the defectives. Apart from the combinatorial guarantees, it is often of key interest to equip measurement designs with efficient decoding algorithms. The most efficient decoders should run in sublinear time in n, and ideally near-linear in the number of measurements m.

In this work, we give several constructions with an optimal number of measurements and near-optimal decoding time for the most fundamental group testing tasks, as well as for central tasks in the compressed sensing and heavy hitters literature. For many of those tasks, the previous measurement-optimal constructions needed time either quadratic in the number of measurements or linear in the universe size.

Among our results are the following: a construction of disjunct matrices matching the bestknown construction in terms of the number of rows m, but achieving nearly linear decoding time in m; a construction of list disjunct matrices with the optimal m = O(k log(n/k)) number of rows and nearly linear decoding time in m; error-tolerant variations of the above constructions; a non-adaptive group testing scheme for the "for-each" model with m = O(k log n) measurements and O(m) decoding time; a streaming algorithm for the "for-all" version of the heavy hitters problem in the strict turnstile model with near-optimal query time, as well as a "list decoding" variant obtaining also near-optimal update time and O(k log(n/k)) space usage; an ℓ 2 /ℓ 2 weak identification system for compressed sensing with nearly optimal sample complexity and nearly linear decoding time in the sketch length.

Most of our results are obtained via a clean and novel approach that avoids list-recoverable codes or related complex techniques that were present in almost every state-of-the-art work on efficiently decodable constructions of such objects.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. ℓ2/ℓ2 Sparse Recovery via Weighted Hypergraph PeelingNick Fischer, Vasileios NakosFOCS 2025 · 1 citation

Builds on3

  1. Solving tall dense linear programs in nearly linear timeJan van den Brand, Yin Tat Lee, Aaron Sidford, Zhao SongSTOC 2020 · 59 citations
  2. Top-k-convolution and the quest for near-linear output-sensitive subset sumKarl Bringmann, Vasileios NakosSTOC 2020 · 18 citations
  3. Faster Update Time for Turnstile Streaming AlgorithmsJosh Alman, Huacheng YuSODA 2020 · 4 citations

Related papers

  1. Scalable and Efficient Non-adaptive Deterministic Group TestingDariusz R. Kowalski, Dominik PajakNeurIPS 2022 · 1 citation
  2. A MaxSAT-Based Framework for Group TestingLorenzo Ciampiconi, Bishwamittra Ghosh, Jonathan Scarlett, Kuldeep S. MeelAAAI 2020 · 14 citations
  3. List-Decodable Sparse Mean Estimation via Difference-of-Pairs FilteringIlias Diakonikolas, Daniel Kane, Sushrut Karmalkar, Ankit Pensia et al.NeurIPS 2022 · 16 citations
  4. Polynomial Data Structure Lower Bounds in the Group ModelAlexander Golovnev, Gleb Posobin, Oded Regev, Omri WeinsteinFOCS 2020 · 1 citation
  5. Efficient list-decoding with constant alphabet and list sizesZeyu Guo, Noga Ron-ZewiSTOC 2021 · 21 citations
Dusk over the sea between two cliffs drawn in fine vertical lines