\section{Preliminaries}
\label{sec:prelim}

\subsection{Notation}

\newcommand{\bpref}{\mathsf{bPref}}

When referring to group testing, all matrices and vectors have entries in $\{0,1\}$, with $0$ corresponding to ``false'' and $1$ to ``true''. Without loss of generality, we can assume that $k,n$ are powers of two by rounding to the closest power of two from above, unless noted otherwise. We will associate $[n] := \{0, \ldots, n-1\}$ with $\{0,1\}^{\log n}$ via the obvious bijection. Moreover, all matrices and vectors are zero-indexed, that is for vector $x \in \{0,1\}^n$ the entries are $x_0,x_1,\ldots,x_{n-1}$.
More generally, for a set $\mathcal{I} \subseteq [n]$,
we denote by $x_{\mathcal{I}}$ the vector obtained by discarding the entries of $x$ outside $\mathcal{I}$. We also denote the \emph{support} of a vector by $\mathrm{supp}(x) = \{ i \in [n]\colon x_i =1 \}$. 
For binary strings $r,s$, we write $r\| s$ to be the concatenation of $r$ and $s$ by writing $r$ followed by $s$.
For a test matrix $ M \in \{0,1\}^{m \times n}$ (where the number of columns $n$ is called the \emph{population} or the \emph{universe} size), and a vector $x \in \{0,1\}^n$, the vector $ y = M \odot x $ corresponds to tests 
\begin{align*}
y_q = \bigvee_{j \in [n]\colon M_{q,j} =1 } x_j, \forall q \in [m],
\end{align*}
where $M_{q,j}$ denotes the entry of $M$ at row $q$ and column $j$.


For $ i \in [n]$ we denote by $M^i$ the $i$-th column of $M$ and $M_i$ to be the $i$-th row of $M$. For $S \subseteq [n]$, we define $M^S = \bigcup_{i \in S} M^i$. Clearly $M^i = M^{\{i\}}$. 

When referring to heavy hitters or compressed sensing we will work with the standard notion of addition and multiplication on numbers of $\Theta(\log n)$ bits. We will say that $i$ is a $(1/k)$-heavy hitter for the vector $x \in \mathbb{R}^n$ if $|x_i| \geq (1/k)\|x\|_1$. We define $\|x\|_p = \left( \sum_{i=0}^{n-1} |x_i|^p \right)^{1/p}$. 
We denote by $x_{-k}$ the \emph{tail} vector that occurs after zeroing out the $k$ largest in magnitude coordinates in $x$. 

For non-negative integers $\alpha, \ell$ such that $\alpha \leq 2^{\ell}-1$, we denote by $\bpref_{\ell}(\alpha)$ to be the integer that is obtained from the first $\ell$ bits in the binary representation of $\alpha$. For example, $\bpref_{2}( (1100)_2 ) = (11)_2 = 3$, and $\bpref_3( (11011)_2 ) = (110)_2 = 6$, where we have used the notation $(\cdot)_2$ for the  binary representation of an integer).

\subsection{Catalan Numbers}
We shall use the following fact on Catalan numbers.

\begin{lemma}[generalized Catalan numbers, \cite{sloane2007line}]\label{lem:estimation_catalan}
For natural integers $d,n\geq 2$, the number of rooted $d$-ary trees with exactly $n$ nodes is 
\[\mathrm{Cat}_n^d = \frac{1}{n+1}  {d n\choose n} \leq (ed)^n.\]
\end{lemma}

\subsection{Disjunct and List-Disjunct Matrices}

In this section, we review the standard notion of disjunctness and
its variations that are instrumental
for the design of group testing schemes (cf.\ \cite[Chapter~4]{du2000combinatorial}).

\begin{definition}[Disjunct Matrices] \label{def:disjunct} 
A matrix $M \in \{0,1\}^{m \times n}$ is called $k$-disjunct if for every set $S \subseteq [n]$ of size $k$, and every $j \in [n] \setminus S$ there exists a row $q \in [m]$ such that $M_{q,j} =1 $ and $M_{q,j'}=0, \forall j' \in S$.
\end{definition}

A $k$-disjunct matrix essentially characterizes the combinatorial guarantee
needed for noiseless group testing. The relaxes notion of \emph{list-disjunct}
matrices guarantees identification of a bounded-sized superset of
the defective (thereby allowing a smaller number of rows by 
only requiring the recovery of 
a small list that is guaranteed to contain all defectives). The following
definition is from \cite{indyk2010efficiently} (while an essentially equivalent
notion was formulated in \cite{ch2009noise}).

\begin{definition}[List-Disjunct Matrices] 
A matrix $M \in \{0,1\}^{m \times n}$ is called a $(k,\ell)$-list-disjunct matrix if for every two disjoint sets $S,T \subseteq [n]$ with $|S|=k, |T|=\ell+1$ there exists an element $j \in T$ and a row $q \in [m]$ such that 

	\[	M_{q,j} =1~\mathrm{and}~\forall j'\in S, M_{q,j'}=0.		\]
\end{definition}

The parameter $\ell$ captures the \emph{list size} (so that it is always possible
to output a list of size at most $k+\ell$ that contains the defective). 
For $\ell=0$ the notion of list-disjunct matrices
coincides with the classical notion of disjunct matrices (Definition~\ref{def:disjunct}).
Given the measurement outcomes, one can naturally consider a list of
possible defectives by selecting all columns of $M$ the are covered
by the vector of the measurement outcomes.  More precisely,
we can define the following.


 \begin{definition}[Associated List for List-Disjunct Matrices]
Given $y = M\odot x$ with $M$ being $(k,\ell)$-list-disjunct matrix and $|\mathrm{supp}(x)| \leq k$, we will refer to $L$ as the \emph{associated list} of $x$ with respect to $M$ as the list of elements $i \in [n]$ satisfying the following:

	\[	\forall q \in [m] \text{ such that } y_q = 1\colon M_{q,i} = 1.\] 
Put simply, $L$ corresponds to the elements $i \in [n]$ which appear to be ``defective'' under measurements defined by $M$. Note that $|L| \leq k+\ell$.
\end{definition}

The above notions can be strengthened to tolerate errors as follows:


\begin{definition}\cite[Definition~1]{icalp11}
A matrix $M \in \{0,1\}^{m \times n}$ is called $(k,\ell,e_0,e_1)$-list disjunct if for every 
disjoint sets $S, T \subseteq [n]$ of size $k$ and $\ell$, respectively, the following
holds. Let $M^S$ and $M^T$ respectively denote the unions of supports of the 
columns of $M$ picked by $S$ and $T$. Then, for 
every set $X \subseteq M^T \setminus M^S$ of size $|X| \leq e_0$,
there is a column $M^j$ picked by $T$ such that
$|\supp(M^j) \setminus (X \cup M^S)| > e_1$.
\end{definition}

In the above definition, $e_0$ (resp., $e_1$) captures the number of false positives
(resp., negatives) that the matrix $M$ can combinatorially 
tolerate in the measurement outcomes (and in the sequel, this is what we 
would mean by a matrix tolerating a certain number of false positives or negatives).
We could have alternatively used the notion of error-correcting disjunct matrices in (\cite[Definition~1]{ch2009noise}), but since our results behave differently in the case of false positives and false negatives, the definition in~\cite{ch2009noise} is not the most suitable for our needs. We refer the reader to Theorems \ref{thm:error_list}~and~\ref{thm:error_dis} for the results on error-correcting $k$-disjunct matrices.	

It is shown in \cite[Proposition~2]{icalp11} that any $(k,\ell,e_0,e_1)$-list disjunct matrix 
guarantees recovery of a set of size less than $k+\ell$ containing all defective
items in presence of up to $e_0$ false positives and $e_1$ false negatives in the
test outcomes. Lower bounds in~\cite{ch2009noise,icalp11} show that $(k,\Theta(k),e_0,e_1)$-error-correcting list-disjunct matrices require $\Omega( k\log(n/k) + e_0 + ke_1)$ rows. Similarly, any $k$-disjunct matrix that can tolerate $e_0$ false positives and $e_1$ false negatives requires $\Omega( k^2\log_k n + e_0 + ke_1)$ rows.


A natural decoder for disjunct and list-disjunct matrices is the following, often referred to as the \emph{naive~decoder}.
\begin{definition}[Naive Decoder]\label{def:naive}
Given $y = M \odot x$, for every $i \in [n]$ declare $i$ defective if and only if $y_r=1$ for every $r$ such that $M_{r,i}=1$. That is, output the set of columns that
are covered by the measurement outcomes.
\end{definition}
The following are two well-known corollaries on the performance of the naive decoder in disjunct and list-disjunct matrices. 
\vspace{-2mm}
\begin{lemma}[Naive Decoder and Point-Queries for Disjunct Matrices] \label{lem:point_query_disjunct}
Given $y= M\odot x$, where $M$ is a $k$-disjunct matrix and $|\mathrm{supp}(x)| \leq k$ the following holds. Given $i \in [n]$, we can decide in time $O(|\mathrm{supp}(M^i)|)$ whether $i$ is defective or not. Moreover, the naive decoder returns $\mathrm{supp}(x)$ in time $O(n \cdot \mathrm{max}_{i \in [n]}|\mathrm{supp}(M^i)|)$.
\end{lemma}

\begin{lemma}[Naive Decoder and Point-Queries for List-Disjunct Matrices] \label{lem:point_query_list_disjunct}
Given $y = M\odot x$, where $M$ is a $(k,\ell)$ list-disjunct matrix, and $|\mathrm{supp}(x)| \leq k$ the following holds. Given $i \in [n]$ we can decide whether $i$ belongs to the associated list $L$ in time  $O(|\mathrm{supp}(M^i)|)$ whether $i$ is defective or not. Moreover, the naive decoder returns $L$ in time $O(n \cdot \mathrm{max}_{i \in [n]}|\mathrm{supp}(M^{i})|)$.


\end{lemma}

We shall use the following well-known constructions of $k$-disjunct matrices, which follows from standard constructions of incoherent matrices (based on either Reed-Solomon codes by Kautz and Singleton \cite{ref:KS64} or codes on the Gilbert-Varshamov bound \cite{porat2008explicit} by Porat and Rothschild)\footnote{
The construction of \cite{ref:KS64} is strongly explicit, in the sense that each entry
of the matrix can be computed in $\poly(k, \log n)$ time, whereas \cite{porat2008explicit}
is explicit in the sense of being computable in $\poly(n)$ time.}

\begin{theorem}[Disjunct Matrices]\label{thm:disjunct_tool}
There exists a $k$-disjunct matrix with 
\[m = O(k^2 \mathrm{min}\left\{\log n, (\log_k n)^2 \right\})\]
rows. In particular, there exist explicit $k$-disjunct matrices with i) $O(k^2 \log n)$ rows and $O(k \log n)$ non-zeros per column (via \cite{porat2008explicit}), and strongly explicit
$k$-disjunct matrices with ii) $O(k (\log_k n)^2 )$ rows and $O( k \log_k n)$ non-zeros per column (via \cite{ref:KS64}).

\end{theorem}


We will use the following existential bound on list-disjunct matrices, that can be
derived from \cite{ch2009noise} via a probabilistic argument: 
\begin{theorem}[\cite{ch2009noise}]\label{thm:list_disjunct_tool}
There exists a $(k,k)$-list-disjunct matrix with $O(k \log (n/k))$ rows and $O(\log(n/k))$ non-zeros per column.
\end{theorem}
{"config": "arxiv", "file": "2006.08420/preliminaries.tex"}