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

Background

• The standard group-testing setup uses non-adaptive tests, and list-disjunct matrices can reduce row counts by essentially a factor of k relative to disjunct matrices.Efficient decoding is desirable because the naive decoder scans the universe and can be exponentially slower than recovery scaled to the number of tests.Source: §1 · pp. 3–4

Combinatorial Group Testing

• The list-disjunct construction uses O(k log(n/k)) rows and decodes in O(k log^2(n/k)) time, settling its measurement and decoding-time complexity.The best previous sublinear-time scheme using an optimal number of measurements had quadratic decoding time in k.Source: §1 · p. 5
• The paper gives explicit k-disjunct matrices with O(k^2 log n) rows and decoding time nearly linear in the number of rows.It also reports state-of-the-art error-correcting disjunct and list-disjunct matrices whose decoders are faster by almost a factor k at the same row count.Source: §1 · p. 5
• The paper presents a “for-each” group testing scheme with O(k log n) decoding time and measurements, improving on recent work with quadratic-in-k decoding time.The scheme is necessarily randomized.Source: §1 · p. 5

Heavy Hitters

• The paper gives a “for-all” strict-turnstile heavy hitters algorithm using O(k log(n/k)) space, with near-linear query time and eO(log^2 k · log(n/k)) update time.It finds a list of size O(k) containing all (1/k)-heavy hitters; the previous same-space algorithm required Ω(n log n) query time.Source: §1 · pp. 5–6
• For the standard strict-turnstile heavy hitters problem, the paper matches previous space usage while reducing query time to near-linear in that space.Previous constructions had Ω(nk) query time.Source: §1 · p. 6

Compressed Sensing

• The paper presents a significantly stronger ℓ2/ℓ2 weak identification system than was previously available in compressed sensing.Source: §1 · p. 6

Unifying Approach

• A unifying result gives a row-optimal (k, 5k log(n/k))-list-disjunct matrix with an efficient decoder, without relying on list-recoverable-code techniques.The authors note that the approach requires minimal coding-theory understanding compared with those techniques.Source: §1 · p. 6

2.1 Notation

• The notation uses binary group-testing matrices and vectors, zero-based indexing, restricted subvectors, supports, string concatenation, and defines x−k by zeroing its k largest-magnitude coordinates.Source: §2.1 · pp. 6–7

2.2 Catalan Numbers

• The section states a generalized Catalan-number fact for counting rooted d-ary trees with exactly n nodes.The passage supplies the lemma’s statement but not its displayed count.Source: §2.2 · p. 7

2.3 Disjunct and List-Disjunct Matrices

• Disjunct matrices isolate each non-defective column from any k-column set, while list-disjunct matrices permit a bounded candidate list and can use fewer rows.The associated list has size at most k + ℓ; the naive decoder returns it in O(n · maxi∈[n]|supp(Mi)|) time, whereas point queries take O(|supp(Mi)|) time.Source: §2.3 · pp. 7–8
• The preliminaries describe error-correcting list-disjunct matrices as tolerating specified false positives and false negatives, with corresponding lower bounds on required rows.For (k, Θ(k), e0, e1)-error-correcting list-disjunct matrices the stated lower bound is Ω(k log(n/k) + e0 + ke1) rows.Source: §2.3 · p. 8

3.1 Disjunct and List-Disjunct Matrices

• List-disjunct constructions achieve O(k log(n/k)) rows, with decoding in O(k log(n/k)) time for a larger list or O(k log²(n/k)) time for a (k,k)-list-disjunct matrix.The first construction also tolerates up to C_FP·k false positives per submatrix.Source: §3 · p. 9, §3.1 · p. 9
• Monte-Carlo k-disjunct matrices use O(k² min{log n, (log_k n)²}) rows and decode in O(m + k log²(n/k)) time.An explicit construction uses O(k² log n) rows and m·poly(log n) decoding; rounding extends the row bound to k^(2+o(1)) log n for all k.Source: §3.1 · p. 10

3.2 Heavy Hitters in the Strict Turnstile Model

• Strict-turnstile streaming results use O(k log(n/k)) space for heavy-hitter lists with sublinear query time, including a variant that excludes low coordinates and estimates returned values.For returned coordinates, the estimate lies between x_i and x_i + (c/k)||x||_1, for arbitrarily small absolute c < 1.Source: §3.2 · pp. 10–11

3.3 Error-Correcting Disjunct Matrices

• False-positive constructions tolerate e0 errors with O(k log(n/k) + log_k(n)e0) rows for list-disjunct matrices, or O(k² log n + log_k(n)e0) rows for disjunct matrices; false-negative constructions tolerate k·e1 errors with O(k² log n + k·e1) rows.The false-negative result is described as achieving the optimal dependence on e1.Source: §3.3 · pp. 11–12

3.4 Resolving the “For-Each” Case of Group Testing

• A randomized for-each group-testing scheme uses O(k log n) measurements and decoding time, improving on prior work with the same row count and quadratic-in-k running time.The authors say this essentially settles the non-uniform case.Source: §3.4 · p. 12

3.5 ℓ2/ℓ2 Compressed Sensing

• For ℓ2/ℓ2 compressed sensing, the authors report the first near-optimal weak identification system with near-optimal decoding time, without an additional inversion table.They describe a stronger result for the general problem but leave it for future publication.Source: §3.5 · p. 13

Overview of Techniques and Comparison with Previous Work

• Bit-masking can make disjunct or list-disjunct testing sublinear-time, but its logarithmic-in-n row increase motivates improved trade-offs.The bit-masking-plus-clean-up framework is less effective for recovering all heavy hitters and is inapplicable to group testing, where subtraction is unavailable.Source: §4 · pp. 13, 15
• The method gradually extends prefixes of defective items, seeking a list of size O(k log(n/k)) containing all defectives rather than immediately identifying them.It processes prefix lengths in increasing order and discards prefixes that do not participate in a positive test.Source: §4 · p. 14
• Unlike list-recoverable codes, the method uses lists that depend on the hidden defective set and form serially as bits are learned in chunks.The authors argue this avoids the codes’ requirement that a condition hold for all choices of symbol lists.Source: §4 · p. 15
• Tree codes require worst-case Hamming-distance guarantees between every pair of strings, while this approach needs an average-distance bound.The paper describes the tree-code condition as too strong and inflexible for its group-testing construction.Source: §4 · p. 15
• List-recoverable-code techniques can improve measurement bounds in the for-all model, but usually require polynomial-in-k decoding time and complicated algorithms.Prior approaches connect group-testing matrices to list-recovery, including through extractors, expanders, and code concatenation [Che12].Source: §4 · pp. 14–15
• The approach adds a sparse-recovery framework for essentially optimal results that previous arguments could not obtain, with future progress potentially coming from hybrids of frameworks.The authors describe their list construction as avoiding the for-all demand of list-recoverable codes.Source: §4 · pp. 15–16

5 Construction of the Identification Matrix

• The Monte Carlo identification matrix has at most Ck log(n/k) rows and concatenates matrices M(ℓ) across prefix lengths from log k to log n.Each matrix M(ℓ) consists of Ck rows.Source: §5 · p. 16
• The construction takes n to be a power of two and identifies its items with binary strings of length log n.The matrix M is the vertical concatenation of the level-specific matrices.Source: §5 · p. 16
• At each level ℓ, items agreeing on their first ℓ binary bits share a row determined by hashing their prefix into one of Ck buckets.The construction uses a random function hℓ from ℓ-bit prefixes to the bucket range.Source: §5 · p. 16

6 Decoding Algorithm Analysis and Proof of Theorem 3.1

• Every defective item remains in the output list because its prefix always participates in a positive test and is not discarded.The argument follows the item’s prefixes through the levels until ℓ = log n.Source: §6 · p. 17
• With probability at least 1 − e^−C1k log(n/k), the output list has at most CLk log(n/k) + k items despite CFPk adversarial false positives per matrix, and decoding takes O(k log(n/k)) time.The probability bound is over the hash functions used at the different levels.Source: §6 · p. 17
• The analysis models decoding as a forest of candidate-prefix trajectories and bounds the non-defective portion to control list size and running time.The proof bounds the trajectory size with high probability, then derives the output-list and runtime bounds.Source: §6 · pp. 17–18
• Starting from prefixes of length log k, the decoder tests each candidate and extends it by one bit when it is not discarded.Algorithm 2 fetches the measurement indexed by the hashed prefix and extends surviving prefixes with both possible next bits.Source: §6 · pp. 17–18
• The hash functions can be packed into one limited-independence function, with fast multipoint polynomial evaluation supporting the stated implementation.The proof uses a machine word size of Ω(log n) for constant-time indexing and string concatenation.Source: §6 · pp. 16, 19

7 Obtaining Optimal Monte Carlo Constructions

• Theorem 3.2 filters the O(k log(n/k))-size list from Theorem 3.1 using O(log(n/k)) time per element.The construction augments the identification matrix with the matrix from Theorem 2.10.Source: §7 · p. 19
• Theorem 3.3 combines matrices to use O(k^2 min{log n, (log_k n)^2}) rows and O(k log^2(n/k) + m) running time.The proof gives separate point-query time bounds for the two alternatives in Theorem 2.9.Source: §7 · pp. 19–20
• Theorem 3.5 finds a list of O(k log(n/k)) containing every (1/k)-heavy hitter, then filters it to O(k) items using point queries.The construction uses the identification matrix, an [LNW18] matrix, and an all-ones row to obtain ∥x∥1.Source: §7 · p. 20
• Theorem 3.5’s low-space streaming implementation uses buffered updates to de-amortize update costs, with a query-time increase of O(k poly(log n)).The passage gives worst-case update and query bounds after the buffer-based de-amortization.Source: §7 · p. 20
• A turnstile ℓ1-heavy-hitter scheme uses O(k^2 log^2 n) space and O(m log n) query time without assuming nonnegative coordinates.The passage says the same guarantee was already obtainable by bootstrapping the incoherent matrix of [NNW12], while this approach avoids error-correcting-code machinery.Source: §7 · p. 21
• For Theorem 3.10, augmenting the identification matrix with two matrices filters an O(k log(n/k))-size list to O(k) candidates, then identifies defectives in O(k log n) time.The first filtering stage succeeds with probability 1 − e^−Ω(k).Source: §7 · p. 21

• Optimal-row explicit list-disjunct matrices may be out of reach, since known explicit constructions rely on expander graphs and list-disjunctness is closely connected to expansion.Source: §8 · p. 22
• The section also gives an explicit k-disjunct construction via incoherent matrices, while identifying average Hamming distance after a split point as a derandomization challenge.Source: §8 · p. 22
• For k = O(log n / log log n), Theorem 8.1 gives O(k^2 log n) rows and decoding time poly(k, log n).Source: §8 · p. 22
• For larger k, a hierarchical prefix search uses list-disjunct matrices at successive levels and maintains an O(k)-size list containing every defective.The construction uses D = log n / log log n levels and extends matrices over prefixes to the full universe.Source: §8 · pp. 22–23
• For the naive decoder, list-disjunctness bounds the candidate list in the same way expansion bounds the set of left vertices whose neighbors lie in a given right-vertex set.Source: §8 · p. 22
• O(k^2 log n) rows and O(k^2 log n) decoding time are achieved by the construction for the regime of interest.Source: §8 · p. 23

9 Error-Correcting Disjunct and List-Disjunct Matrices (Proof of Theorems 3.8 and 3.9)

• Theorem 9.1 gives error-correcting list-disjunct and disjunct matrices with stated measurement and column-sparsity bounds [Che12, NPR11].The list-disjunct matrix uses O(k log(n/k) + e0 + ke1) rows and column sparsity O(log(n/k) + e0/k + e1); the k-disjunct matrix uses O(k^2 log n + e0 + ke1) rows and column sparsity O(k log n + e0/k + e1).Source: §9 · pp. 23–24

9.1 Proof of Theorem 3.8

• Theorem 3.8’s construction outputs a list of size O(k log_k(n/k)) in O(k^(1+α) log(n/k)) time, under k log k false positives.The output list contains every defective item, and the stated bounds hold with probability 1 − e^(−C1 k log(n/k)).Source: §9.1 · pp. 25–26
• Theorem 3.8’s second claim filters non-defectives by augmenting its matrix with the disjunct matrix from Theorem 9.1.A separate reduction gives a list-disjunct matrix with O(k log(n/k) + log(n/k) · e0) rows and O(m log m) decoding time.Source: §9.1 · p. 27

9.2 Proof of Theorem 3.9

• Lemma 9.4 states an existence guarantee: a (k, O(k), e0, 0)-error-correcting list-disjunct matrix has m = O(k^2 log n + ke1) rows and allows decoding in time m · poly(log n).Source: §9.2 · p. 28
• The approach performs poorly with false positives and requires Θ(k) repetitions to enable a union bound, producing a quadratic measurement bound.An adversary with e0 = Θ(k^2 log n) false positives can overload the bucket matrices containing a defective item and prevent its detection.Source: §9.2 · pp. 30, 32
• The stand-alone reduction avoids list-recovery technology, converting a list-disjunct matrix correcting e1 false negatives into a disjunct matrix tolerating those errors.Given a (k, O(k), 0, e1)-error-correcting list-disjunct matrix with R rows and polynomial-time decoding for k ≤ c log n, Lemma 9.7 constructs a k-disjunct matrix for k > c log n.Source: §9.2 · pp. 30–31
• m = O(k^2 log n + k e1) rows suffice for an error-correcting (k, n, e1)-disjunct matrix, decodable in m · poly(log n) time for all k.This bound follows when R(k, n, e1) = O(k log(n/k) + k e1); for k ≤ c log n, a list of size 2k is filtered using Theorem 9.1.Source: §9.2 · p. 31
• Hashing items into buckets, decoding each bucket's logarithmic-sparsity list-disjunct matrix, and retaining items returned in most repetitions yields an O(k)-sized list for exact filtering.The reduction decodes each bucket matrix with error tolerance e1/k and uses Theorem 9.1 to identify the defectives from the resulting list.Source: §9.2 · p. 31

10 ℓ2/ℓ2 Compressed Sensing

• The randomized construction yields a candidate list of size C_T(k/ε) log(n/k), and its decoder runs in O(m log^2 n) time.The list contains a subset T of at most k coordinates satisfying the lemma’s recovery guarantee.Source: §10 · pp. 33–34
• A coupling argument handles dependent failure indicators by dominating them with jointly independent Bernoulli variables before applying a Chernoff bound.The dependence arises when prefix estimates share measurements; the independent variables stochastically dominate the original indicators.Source: §10 · p. 35
• All but k/10 coordinates in H are returned in the list with probability 1−δ², while potentially false prefixes are bounded by O((k/ε) log(n/k)).H comprises coordinates among the top k whose magnitudes meet the stated threshold relative to the tail norm.Source: §10 · pp. 34, 35, 37
• A CountSketch stage prunes the candidate list to 2k coordinates using median estimates, yielding the stated overall failure probability δ.The construction uses repeated signed sketches and keeps coordinates with the largest-magnitude approximations.Source: §10 · p. 37
• The general ℓ2/ℓ2 scheme is obtained by vertically packing weak systems and iteratively recovering sparse approximations from residual sketches.The passage gives a schedule of decreasing sparsity and approximation parameters for the successive systems.Source: §10 · p. 37

11 Conclusion and Future Work

• The authors present a new sublinear-time framework as a major step toward resolving open problems and improving measurement–decoding trade-offs.They suggest that an error-correcting mechanism layered on their construction may support further progress.Source: §11 · p. 38
• List-disjunct constructions remain more challenging than disjunct ones, since list-disjunct matrices can be used to construct disjunct matrices.The authors point to possible interaction between their ideas and list-recovery methods.Source: §11 · p. 38
• Error-correcting group testing is harder than compressed sensing because its errors are adversarial and it must identify all defectives in one stage.Compressed sensing errors depend on the vector structure, and its recovery can identify most heavy hitters through subtract-and-repeat.Source: §11 · p. 38