Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Combinatorial Group Testing and Sparse Recovery Schemes with
  Near-Optimal Decoding Time   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
\ll n$ disjunctive measurements. In the non-adaptive setting, the most widely
used combinatorial objects are disjunct and list-disjunct 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.
  Most of our results are obtained via a clean and novel approach which avoids
list-recoverable codes or related complex techniques which were present in
almost every state-of-the-art work on efficiently decodable constructions of
such objects.

0
The categories of this paper are: hep-ph
26
The categories of this paper are: bayes-an
14
The categories of this paper are: math-ph
10
The categories of this paper are: q-bio
21
The categories of this paper are: adap-org
3
The categories of this paper are: physics
35
The categories of this paper are: mtrl-th
9
The categories of this paper are: nlin
34
The categories of this paper are: chem-ph
36
The categories of this paper are: cmp-lg
30
The categories of this paper are: q-alg
19
The categories of this paper are: eess
22
The categories of this paper are: chao-dyn
28
The categories of this paper are: alg-geom
31
The categories of this paper are: ao-sci
27
The categories of this paper are: comp-gas