# Efficient Deterministic Quantitative Group Testing for Precise Information
Retrieval††thanks: D. Pajak was supported by the National Science Centre,
Poland—Grant Number 2019/33/B/ST6/02988.

Dariusz R. Kowalski  School of Computer and Cyber Sciences, Augusta
University, USA<EMAIL_ADDRESS>Dominik Pajak  Wrocław University of
Science and Technology, Poland<EMAIL_ADDRESS>
###### Abstract

The Quantitative Group Testing (QGT) is about learning a (hidden) subset $K$
of some large domain $N$ using a sequence of queries, where a result of a
query provides information about the size of the intersection of the query
with the unknown subset $K$. Almost all previous work focused on randomized
algorithms minimizing the number of queries; however, in case of large domains
$N$, randomization may result in a significant deviation from the expected
precision. Others assumed unlimited computational power (existential results)
or adaptiveness of queries. In this work we propose efficient non-adaptive
deterministic QGT algorithms for constructing queries and deconstructing a
hidden set $K$ from the results of the queries, without using randomization,
adaptiveness or unlimited computational power. The efficiency is three-fold.
First, in terms of almost-optimal number of queries – we improve it by factor
nearly $|K|$ comparing to previous constructive results. Second, our
algorithms construct the queries and reconstruct set $K$ in polynomial time.
Third, they work for any hidden set $K$, as well as multi-sets, and even if
the results of the queries are capped at $\sqrt{|K|}$. We also analyze how
often elements occur in queries and its impact to parallelization and fault-
tolerance of the query system.

##  1 Introduction

In the Group Testing field, introduced by [24], the goal is to identify, by
asking queries, all elements of an unknown set $K$. All we initially know
about set $K$ is that $|K|\leq k$, for some known parameter $k\leq n$, and
that it is a subset of some much larger set $N$ with $|N|=n$. The answer to a
query $Q$ depends on the intersection between $K$ and $Q$ and equals to
$\mathsf{Result}(K\cap Q)$, where $\mathsf{Result}$ is some result function
(also called feedback function in this paper). The sequence of queries is a
correct solution to Group Testing if and only if for any two different sets
$K_{1},K_{2}$ (satisfying some cardinality restriction), the sequence of
answers for $K_{1}$ and $K_{2}$ is different. Note that this allows to
uniquely identify the hidden set $K$ based on the results of the queries,
though in some cases such decoding could be a hard computational problem. The
objective is: for a given deterministic feedback function
$\mathsf{Result}(\cdot)$, to find a fixed sequence of queries that will
identify any set $K$ and the length of this sequence, called the query
complexity, will be shortest possible. In particular, we are interested in
solutions that have query complexity logarithmic in $n$ and polynomial in $k$.

The most popular classical variant, present in the literature, considers
function $\mathsf{Result}(\cdot)$ that simply answers whether the intersection
between $K$ and $Q$ is empty or not, c.f., [25]; it is also known under the
name of beeping. Another popular result function returns the intersection
size; this variant has also been studied under the name of _coin weighting_
[2, 21] and Quantitative Group Testing [29, 26]. Those variants were applied
in many domains, including pattern matching [11, 38], compressed sensing [17],
streaming algorithms [16, 14], reconstructing graphs [9, 33], identifying
genetic carriers [3], resolving conflicts on multiple-access channels [4, 5,
28, 34, 35, 42, 44].

In this paper we study the problem of Group Testing under a more general
_capped quantitative result_ , where the result (feedback) is the size of the
intersection up to some parameter $\alpha$ and $\alpha$ for larger
intersections. It subsumes and generalizes the two previously described
classical result functions: the smallest possible case of $\alpha=1$
corresponds to the classical empty/non-empty feedback (beeping), while the
case $\alpha=k$ captures the (full) quantitative feedback. For this
generalized result function we study the influence of the parameter $\alpha$
on the optimal query complexity of Group Testing – thus giving a formal
explanation why different settings considered in the literature differ in
terms of the query complexity, i.e., the optimal length of query sequence
allowing to decode a hidden set from feedbacks.

Our focus is on non-adaptive solutions, in which queries must be fixed and
allow to discover any hidden set based on capped quantitative feedback. Such
solutions could be seen as codes: each element corresponds to a binary
codeword with $0$ or $1$ on $i$-th position indicating whether the element
belongs to $i$-th query. Our main emphasis in on minimization of code length
and _polynomial-time construction of queries/codewords allowing polynomial-
time decoding of the hidden set_. All existing polynomial
construction/reconstruction algorithms for beeping or quantitative feedbacks
produce codes of length $\Theta(\min\\{n,k^{2}\log n\\})$, c.f., [45]. General
constructions developed in this work, when instantiated for a specific
feedback parameter $\alpha\in[k]=\\{1,\ldots,k\\}$, shrink the gap for
efficiently constructed query systems even exponentially, and together with
the lower bound – explain why sometimes a much smaller feedback is sufficient
for decoding sets with similar efficiency.

###  1.1 Our results

$\alpha$ | Constructive Upper Bound | Existential Upper Bound | Lower bound
---|---|---|---
$1$ |  $O(k^{2}\log n)$ [45] |  $O\left(k^{2}\log\frac{n}{k}\right)$ [19] |  $\Omega\left(k^{2}\frac{\log n}{\log k}\right)$ [10]
$k$ |  |  $O(k^{2}\log n)$ [45]
---
$\widetilde{O}(k)$ Thm 1
$O\left(k\frac{\log n}{\log k}\right)$[33] |  $\Omega\left(k\frac{\log n}{\log k}\right)$ (folklore)
$*$ |  | $\widetilde{O}\left(\min\left\\{\left(\frac{k}{\alpha}\right)^{2},\frac{n}{\alpha}\right\\}+k\right)$
---
Thm 1
| $O\left(\min\left\\{n,\left(\frac{n}{\alpha}+k\right)\log n\right\\}\right)$
---
if  $k>\sqrt{n\alpha}$, Thm 3
|
$\Omega\left(\min\left\\{\left(\frac{k}{\alpha}\right)^{2},\frac{n}{\alpha}\right\\}+k\frac{\log
n}{\log k}\right)$
---
Thm 2
Table 1:  Bounds on query complexity (codeword length) of solutions to non-
adaptive Group Testing with ${\mathcal{F}}_{\alpha}$ feedback. By constructive
upper bound we mean constructive in time $poly(n)$. Symbol $*$ stands for any
valid value of the parameter, notation $\widetilde{O}$ disregards
polylogarithmic factors. Our existential upper bound in Theorem 3 only covers
some range of parameters (it assumes $k>\sqrt{n\alpha}$).

We show the first efficient explicit polynomial-time construction of Group
Testing query sequence, with an associated polynomial-time decoding algorithm
of the hidden set, where the number of queries is only polylogarithmically far
from the absolute lower bound. Previous best polynomial time construction and
decoding algorithms, based on superimposed codes, used super-linearly larger
query complexity (i.e., with super-quadratic length) than the lower bound.
Thus, we shrink the length overhead exponentially, obtaining almost-optimal
number of queries by using efficient polynomial-time coding and decoding
algorithms. We also generalize the result function to _capped result
$F_{\alpha}$_, that returns the size of the intersection only if it is not
bigger than some value $\alpha$. We extend our polynomial time algorithms to
work for any value of $\alpha$. We also prove a lower bound showing that no
other result function capped at $\alpha$, no matter how complex, could allow
substantially less queries (up to a polylogarithmic factor). One of the
consequences of our results is that having quantitative result function capped
at $\alpha=\sqrt{k}$ we obtain similar number of queries as with the full
result (i.e., returning the size of the whole intersection, up to $k$), which
is not a drawback of our method but, as indicated by our lower bound, the
inherited property of Group Testing. We show two applications of our results
in streaming. Our first application is an algorithm that processes a stream of
insertions and deletions of elements and reconstructs exactly the (multi) set
provided that the total number of elements of the set does not exceed $k$. Our
second application is an algorithm for maintaining and reconstructing a graph
with dynamically added or removed edges.

We generalize the classical beeping and quantitative feedbacks by defining an
$\alpha$-capped quantitative feedback function, for any $\alpha\in[k]$:

${\mathcal{F}}_{\alpha}(Q\cap K)=\min\\{|Q\cap K|,\alpha\\}\ ,$

and study the query complexity of non-adaptive Group Testing under this
feedback, where the query complexity is the number of used queries or
alternatively – the length of codewords. We focus on polynomial-time
constructing/decoding algorithms.

#### Main result – Polynomial-time construction/decoding algorithm using
almost optimal number of queries.

Here almost-optimality means that the length of the constructed query sequence
is only polylogarithmically longer than the shortest possible sequence. The
previous best polynomial-time solution used $\Theta(\min\\{n,k^{2}\log n\\})$
queries for all $\alpha\geq 1$ [45], and we shrink it by factor
$\Theta(\min\\{\alpha^{2},k\\}\,\mbox{polylog}^{-1}\,n)$. To achieve this
goal, we define and build new types of selectors, called (Strong) Selectors
under Interference. We also generalize the concept of Round-Robin query
systems, where each query is a singleton, to $\alpha$-Round-Robin query
systems, containing sets of size at most $\alpha$. Such sequences are shorter
than the simple Round-Robin, i.e., have length $O((n/\alpha){\rm\ polylog\
}n)$, and, unlike a simple Round-Robin singletons’ structure, are challenging
to construct in a way to allow correct decoding based on $\alpha$-capped
feedback.

######  Theorem 1.

There is an explicit polynomial-time algorithm constructing non-adaptive
queries $Q_{1},\ldots,Q_{m}$, for
$m=O\left(\min\left\\{\left(\frac{k}{\alpha}\right)^{2}\log^{3}n,\frac{n}{\alpha}{\rm\
polylog\ }n\right\\}+k{\rm\ polylog\ }n\right)$, that solve Group Testing
under feedback ${\mathcal{F}}_{\alpha}$ with polynomial-time decoding.
Moreover, every element occurs in $O(\frac{k}{\alpha}\log^{2}n+{\rm\ polylog\
}n)$ queries, and the decoding time is
$O(m+\frac{k^{2}}{\alpha}\log^{2}n+k{\rm\ polylog\ }n)$.

In Section 5, we describe several non-straightforward applications of this
result to dynamic graph maintenance and Group Testing on multi-sets; other
potential applications include more efficient algorithms for finding hot
elements in online streaming [17] or for wireless communication [34].

#### Lower bound.

The almost-optimality of our algorithms from Theorem 1 is justified by proving
an absolute lower bound on the length of sequences allowing to decode a hidden
set based on feedback ${\mathcal{F}}_{\alpha}$ to the queries. Here by
“absolute” we mean that it holds for all query systems that allow for decoding
of the hidden sets based on feedback ${\mathcal{F}}_{\alpha}$, not restricted
to polynomially constructed queries with polynomial decoding algorithm. Even
more, some components of the lower bound are general: they hold for any
$\alpha$-capped feedback function, which will be formally defined later in
Section 3. The lower bound has three components: $(k/\alpha)^{2}$, $n/\alpha$,
and $k\frac{\log\frac{n}{k}}{\log\alpha}$. For different ranges of $k$,
different components determine the value of the lower bound. Note that these
components match the corresponding components in our constructive upper bound
(Main result in Theorem 1), up to polylogarithmic factor.

######  Theorem 2.

Any non-adaptive algorithm solving Group Testing needs:

  * •

$\Omega\left(\min\left\\{\left(\frac{k}{\alpha}\right)^{2},\frac{n}{\alpha}\right\\}+k\frac{\log\frac{n}{k}}{\log\alpha}\right)$
queries under feedback ${\mathcal{F}}_{\alpha}$.

  * •

$\Omega\left(\min\left\\{\left(\frac{k}{\alpha}\right)^{2},\frac{n}{\alpha}\right\\}\right)$
queries under any feedback capped at $\alpha$.

Component $k\frac{\log\frac{n}{k}}{\log\alpha}$ in the lower bound follows
from a standard information-theoretic argument. To show the remaining parts we
use the following idea. Any algorithm working for any set $K$ must ensure that
each element $x\in K$ belongs to at least one query $Q$ with small
intersection, $|K\cap Q|\leq\alpha$. Otherwise, the element $x$ could be
_jammed_ by other elements and algorithm would not “notice” if it was removed
from $K$. With this observation, we obtain that either the algorithm decides
to place most of the elements in small queries (i.e., of size at most
$\alpha$) or each element has to belong to many queries. In the first case we
easily obtain the necessity of $\Omega(n/\alpha)$ queries. In the second case,
we pick set $K_{1}$ with $k/2$ elements not belonging to any small query and
observe that each of the queries to which these elements belong, can be jammed
by careful selection of $k/2$ elements in $K\setminus K_{1}$. This means that
for each element $v\in K_{1}$ we must have at least $\Theta(k/\alpha)$ queries
containing $v$ and intersecting $K_{1}$ on at most $\alpha$ elements, as
otherwise element $v$ could be jammed by the remaining $k/2$ elements (in
$K\setminus K_{1}$) by simply choosing $\alpha$ elements from each query to
which $v$ belongs. Using this observation we can apply the following counting
argument: for each of $k/2$ elements in $K_{1}$ we have selected
$\Theta(k/\alpha)$ queries and each of these queries can be selected at most
$\alpha$ times (as otherwise it would be jammed already by set $K_{1}$). It
implies $\Omega(k^{2}/\alpha^{2})$ lower bound in this case.

#### Existential result.

Our second upper bound shows the existence of a sequence of queries that
provides unique feedback for any set of at most $k$ elements. It is a non-
constructive version of $\alpha$-Round-Robin (see our Main result in Theorem 1
for $k\in[\sqrt{n\alpha},n/2]$), but it has a smaller polylogarithmic factor.
Its proof is given in Section 8.

######  Theorem 3.

There exists a sequence of queries of length
$O\left(\min\\{n,\left(k+n/\alpha\right)\log n\\}\right)$ solving Group
Testing under feedback ${\mathcal{F}}_{\alpha}$.

This upper bound is shown using the probabilistic method by derandomizing
three claims that the query sequence has to satisfy simultaneously. The first
claim is that each query is small (i.e., has at most $\alpha$ elements) and
the other two claims ensure that some intersection between queries and a
hidden set $K$ will be of size $1$ for two different regimes of parameter $k$.

#### Document structure.

We start from discussing related work on various variants of Group Testing in
Section 2. In Section 3 we formally define the Group Testing problem and the
generalized $\alpha$-capped feedback model. In Section 4 we show our
polynomial-time construction of an algorithm solving Group Testing and prove
that decoding can be done also in polynomial time. In Section 5 we show
applications of our constructions to multisets and graph reconstruction. We
prove the properties of our new selector tools in section 6. In Section 7 we
show the lower bound, while in Section 8 we show the proof of the existential
upper bound. Discussion of results from perspective of future directions is
given in Section 9.

##  2 Previous and related work

In the standard feedback model, considered in most of the Group Testing
literature [25], the feedback tells whether the intersection between query $Q$
and set $K$ is empty or not (sometimes it is also called a beeping model). It
it is a special case ${\mathcal{F}}_{1}$ of our feedback function. In this
feedback model, Group Testing is known to be solvable using
$O(k^{2}\log(n/k))$ [19] queries and an explicit polynomial-time construction
of length $O(k^{2}\log n)$ [45] exists. Best known lower bound (for
$k<\sqrt{n}$) is $\Omega(k^{2}\log n/\log k)$ [10].

The setting considered in this paper is also a generalization of an existing
problem of coin weighting. In the coin weighting problem, we have a set of $n$
coins of two distinct weights $w_{0}$ (true coin) and $w_{1}$ (counterfeit
coin), out of which up to $k$ are counterfeit ones. We are allowed to weigh
any subset of coins on a spring scale, hence we can deduce the number of
counterfeit coins in each weighting. The task is to identify all the
counterfeit coins. Such a feedback is a special case ${\mathcal{F}}_{k}$ of
our feedback function. The problem is solvable with $O(k\log(n/k)/\log k)$
[33] non-adaptive (i.e., fixed in advance) queries and matching a standard
information-theoretic lower bound of $\Omega(k\log(n/k)/\log k)$, as well as
its stronger version proved for randomized strategies [21]. In [2] the author
considers the problem of explicit polynomial-time construction of
$O(k\log(n/k)/\log k)$ queries that allows for polynomial time identification
of the counterfeit coins. However, the algorithm presented in [2] is adaptive,
which means that the subsequent queries can depend on the feedback from the
previous ones. The only existing, constructive, non-adaptive solution would be
using the explicit construction of the superimposed codes [41] but the
resulting query complexity would be $O(k^{2}{\rm\ polylog\ }n)$. Thus, the
solution presented in our paper is the first explicit polynomial time
algorithm constructing non-adaptive queries allowing for fast decoding of set
$K$, with $O(k{\rm\ polylog\ }n)$ fixed queries.

Our algorithms have direct application in stream processing and set
reconstruction. There is a number of existing algorithms retrieving various
informations from streams, such as: extracting the most frequent elements [15,
16, 14, 47], quantile tracking [13, 32, 36], or approximate histogram
maintenance and reconstruction [30, 31]. Some of these existing algorithms use
Group Testing (e.g., [16]) but in a randomized variant. This leads to a small
probability of error that might become significant in very large streams.

An important line of work on non-adaptive randomized solutions to Quantitative
Group Testing [29, 12, 26, 1] resulted in a number of algorithms nearing the
lower bound of $2k\frac{\ln(n/k)}{\ln k}$ [22]. However, these results always
assume some restriction on $k$ (typically $k\sim n^{\theta}$ for some
$0<\theta<1$), and similarly as above, they may result in significant
deviation from the actual set if $n$ is large.

The bounds obtained in this paper match (up to polylogarithmic factors) the
best existing results for the extreme cases of $\alpha=1$ and $\alpha=k$. The
paper also bounds how the query complexity depends on the value of $\alpha$
between these extremes. Interestingly we show, that the shortest-possible
query complexity of $k{\rm\ polylog\ }n$ is already possible for
$\alpha=\sqrt{k}$ and increasing $\alpha$ from $\sqrt{k}$ to $k$ does not
result in further decrease of the query complexity.

The problem of Group Testing has also been considered in various different
feedback models. For instance, [6] shows that $O(k\log\frac{n}{k})$ queries
are sufficient for a feedback that only returns whether the size of the
intersection $|Q\cap K|$ is odd or even. Other interesting feedback function
is a _Threshold Group Testing_ [18], where the feedback model includes a set
of thresholds and the feedback function returns whether or not the size of the
intersection is larger or smaller than each threshold. In [20] the authors
show that it is possible to define an interval of $\sqrt{k\log k}$ thresholds
resulting in an algorithm with $O(k\log(n/k)/\log k)$ queries. Note that both
those feedbacks are “inefficient” in view of our setting of $\alpha$-capped
feedbacks, because their feedback functions are not capped at any $\alpha<k$,
but they achieve similar query complexity as our capped
${\mathcal{F}}_{\sqrt{k}}$ feedback.

Our construction are using known combinatorial tools such as superimposed
codes and dispersers. They were used before in Group Testing [40]. However,
either it led to a super-quadratic (in $k$) number of queries [41, 7] or
decoded only a fraction of elements of the hidden set [39]. In solutions,
where query complexity depends on the number of identified elements, decoding
of all the elements requires over $k^{2}$ queries [19, 8]. In [40], the
authors present the first Group Testing solution with $poly(k,\log n)$
decoding time, but super-quadratic query complexity. It is worth noting that
our generalized solution achieves almost-linear number of queries (for certain
values of $\alpha$) and our decoding algorithm identifies all the elements in
time polynomial in $k$ and logarithmic in $n$. Our use of the known tools is
different then in previous approaches: we define new properties (SuI, SSuI),
which we prove to be satisfied by some combinations of those tools, and lead
to efficient solutions in both query complexity and construction/decoding
time.

##  3 The model and the problem

We assume that the universe of all elements $N$, with $|N|=n$, is enumerated
with integers $1,2,\dots,n$. Throughout the paper, we will associate an
element with its identifier. Let $K$, with $|K|\leq k$, denote a hidden set
chosen arbitrarily by an adversary. Let $\mathcal{Q}=\langle
Q_{1},\ldots,Q_{m}\rangle$ be a non-adaptive algorithm, represented by a
sequence of queries fixed prior to an execution.

Consider feedback function ${\mathcal{F}}_{\alpha}$ that returns the size of
an intersection if it is at most $\alpha$ and $\alpha$ for larger
intersections (i.e., ${\mathcal{F}}_{\alpha}(Q\cap K)=\min\\{|Q\cap
K|,\alpha\\}$). Parameter $\alpha$ in feedback ${\mathcal{F}}_{\alpha}$ is
called a feedback cap. A general class of feedback functions (used in our
lower bound) with feedback cap $\alpha$ includes all deterministic functions
that take subsets of $[N]$ as input and for sets with more than $\alpha$
output some, arbitrary fixed value.

We will say that $\mathcal{Q}$ solves Group Testing, if the feedback vector
allows for unique identification of set $K$. The feedback vector is defined
as:

$\langle{\mathcal{F}}_{\alpha}(Q_{1}\cap K),{\mathcal{F}}_{\alpha}(Q_{2}\cap
K),\dots,{\mathcal{F}}_{\alpha}(Q_{t}\cap K)\rangle$

Thus, in order to solve Group Testing, the feedback vectors for any two sets
$K_{1}$ and $K_{2}$ have to be different. We will say that $\mathcal{Q}$
solves Group Testing with polynomial-time reconstruction if there exists a
polynomial-time algorithm that, given the feedback vector outputs all the
identifiers of the elements from $K$. Finally we will say that $\mathcal{Q}$
is constructible in polynomial time if there exists a polynomial-time
algorithm, that given parameters $n,k,\alpha$ outputs an appropriate sequence
of queries.

We assume that both coupled algorithms, construction and decoding, know
$n,k,{\mathcal{F}}_{\alpha}$. W.l.o.g., in order to avoid rounding in the
presentation, we assume that $n$ and other crucial parameters are powers of
$2$.

Alternatively, we can reformulate the problem of non-adaptive Group Testing
under ${\mathcal{F}}_{\alpha}$ feedback into the language of codes. A query
sequence translates to code as follows: each element $v\in[N]$ corresponds to
a binary codeword with $i$-th position being $1$ or $0$ depending on whether
$v$ belongs to the $i$-th query or not. Then the hidden set $K$ is a subset of
at most $k$ codewords, for which we calculate the feedback vector by taking
the function $\min\\{\cdot,\alpha\\}$ from elementwise sum of all the
codewords corresponding to set $K$. I.e., the feedback is computed for each
position $i$, and the whole feedback vector is an input to the decoding
algorithm. The objective is to decode the elements of $K$ from the feedback
vector.

##  4 Polynomial-time constructions and decoding

###  4.1 Combinatorial tools

In this section we present combinatorial tools used in our constructions. We
introduce two new tools (Selectors-under-Interference and Strong-Selectors-
under-Interference) and use one (Balanced IDs) that has previously been used
in similar contexts.

#### Selector under Interference (SuI).

For given sets $K_{1},K_{2}\subseteq N$ and an element $v\in K_{1}$, we say
that $S\subseteq N$ selects $v$ from $K_{1}$ under $\alpha$-interference from
$K_{2}$ if $S\cap K_{1}=\\{v\\}$ and $|S\cap K_{2}|<\alpha$. Intuitively, $v$
is a unique representative of $K_{1}$ in $S$ and the number of representatives
of $K_{2}$ in $S$ is smaller than $\alpha$. An
$(n,\ell,\epsilon,\kappa,\alpha)$-Selector-under-Interference,
$(n,\ell,\epsilon,\kappa,\alpha)$-SuI for short, is a sequence of queries
$\mathcal{S}=(S_{1},\ldots,S_{x})$ satisfying: for every set $K_{1}\subseteq
N$ of at most $\ell$ elements and set $K_{2}\subseteq N$ of at most $\kappa$
elements, there are at most $\epsilon\ell$ elements $v\in K_{1}$ that are not
selected from $K_{1}$ under $\alpha$-interference from $K_{2}$ by any query
$S_{i}\in\mathcal{S}$, i.e., set $\\{v\in K_{1}\ :\ \forall_{i\leq x}\
S_{i}\cap K_{1}\neq\\{v\\}\mbox{ or }|S_{i}\cap K_{2}|\geq\alpha\\}$ has less
than $\epsilon\ell$ elements.

In Section 6.1 we will describe two polynomial-time constructions of SuI and
prove the following results.

######  Theorem 4.

There is an explicit polynomial-time construction of an
$(n,\ell,\epsilon,\kappa,\alpha)$-SuI, for any $\ell$, any $\alpha\leq k$ such
that $\alpha\ell>c_{2}\kappa$ for a sufficiently large constant $c_{2}$, and
any constant $\epsilon\in(0,1/2)$, of size $O(\min\left\\{n,\ell{\rm\ polylog\
}n\right\\})$. Moreover, every element occurs in $O({\rm\ polylog\ }n)$
queries.

######  Theorem 5.

There is an explicit polynomial-time construction of an
$(n,\ell,\epsilon,\kappa,\alpha)$-SuI, for any $\ell$, any $\alpha\leq\ell$
and $\ell\leq c_{2}\kappa/\alpha$ for a sufficiently large constant $c_{2}$,
and any constant $\epsilon\in(0,1/2)$, of size
$O\left(\min\left\\{n,(\kappa/\alpha){\rm\ polylog\ }n\right\\}\right.$
$\left.+\frac{n}{\alpha}{\rm\ polylog\ }n\right)$. Moreover, every element
occurs in $O({\rm\ polylog\ }n)$ queries.

#### Strong Selector under Interference (SSuI).

An $(n,\ell,\kappa,\alpha)$-Strong-Selector-under-Interference,
$(n,\ell,\kappa,\alpha)$-SSuI for short, is a sequence of queries
$\mathcal{T}=(T_{1},\ldots,T_{x})$ satisfying: for every set $K_{1}\subseteq
N$ of at most $\ell$ elements and set $K_{2}\subseteq N$ of at most $\kappa$
elements, every element $v\in K_{1}$ is selected from $K_{1}$ under
$\alpha$-interference from $K_{2}$ by some query $T_{i}\in\mathcal{T}$, i.e.,
set $\\{v\in K_{1}\ :\ \forall_{i\leq x}\ T_{i}\cap K_{1}\neq\\{v\\}\mbox{ or
}|T_{i}\cap K_{2}|\geq\alpha\\}$ is empty. An $(n,\ell,\kappa,\alpha)$-Strong-
Selector-under-Interference could be also viewed as
$(n,\ell,0,\kappa,\alpha)$-Selector-under-Interference.

In Section 6.2 we will describe a polynomial-time construction of SSuI, which
essentially is a Kautz and Singleton [41] construction for adjusted
parameters, and prove that it satisfies the additional SSuI property.

######  Theorem 6.

There is an explicit polynomial-time construction of an
$(n,\ell,\kappa,\alpha)$-SSuI of length $O(\ell^{2}\log_{\ell}^{2}n)$,
provided $\ell\geq c_{2}\kappa/\alpha$ for some constant $c_{2}$ and for a
sufficiently large constant $c>0$. Moreover, every element occurs in
$O(\ell\log_{\ell}n)$ queries.

#### Balanced IDs.

Each element $i$ in $[n]$ has a unique ID represented by $2\log_{2}n$ bits, in
which the number of 1’s is the same as the number of 0’s; e.g., take a binary
representations of elements $i$ and $n-i$, each in $\log_{2}n$ bits, and
concatenate them. Balanced IDs have previously been used in algorithms for
decoding elements in Group Testing (see e.g., [43]).

###  4.2 Construction of queries, decoding and analysis

#### Algorithm constructing queries.

Let us take $(n,\ell,1/2,k,\alpha-1)$-SuI ${\mathcal{S}}^{(\ell)}$, for $\ell$
being a power of $2$ ranging down from $k$ to $c_{2}k/(\alpha-1)$ (w.l.o.g. we
could also assume that $c_{2}k/(\alpha-1)$ is a power of $2$). Next, for each
set $S$ in these selectors we add the following family
${\mathcal{R}}(S)=\\{R_{i}(S)\\}_{i=1}^{2\log_{2}n}$ of sets $R_{i}(S)=\\{v\in
S\ :\ \lfloor v/2^{i-1}\rfloor=1\mod 2\\}$. Intuitively $R_{i}(S)$ is the set
of elements from $S$ that have $1$ on $i$-th least significant bit of Balanced
ID. Let us call the obtained enhanced selectors (i.e., with additional
families ${\mathcal{R}}(S)$, for every set $S$ in the original selector)
$\bar{{\mathcal{S}}}^{(\ell)}$. Then we concatenate selectors
$\bar{{\mathcal{S}}}^{(\ell)}$, starting from the largest $\ell=k$, to the
smallest value $\ell=c_{2}k/(\alpha-1)$. An
$(n,c_{2}k/(\alpha-1),k,\alpha-1)$-SSuI ${\mathcal{T}}$ is concatenated at the
end, with the same replacement of bits 1 and 0 in the original matrix as in
the above $(n,\ell,1/2,k,\alpha-1)$-SuI’s. Algorithm 1 presents a pseudocode
of the construction algorithm.

1 $\ell\leftarrow k,\mathcal{Q}\leftarrow\langle\rangle$;

2 while  _$\ell >\frac{c_{2}l}{\alpha-1}$_ do

3 $\mathcal{S}\leftarrow(n,\ell,1/2,k,\alpha-1)$-SuI;

4 foreach  _$S\in\mathcal{S}$_ do

5 $\mathcal{Q}$.append$(S)$;

6 for  _$i\leftarrow 1$ to $2\log_{2}n$_ do

/* Add a set of elements from $S$ that have $1$ on $i$-th least significant
bit of Balanced ID. */

7 $R_{i}(S)\leftarrow\\{v\in S\ :\ \lfloor v/2^{i-1}\rfloor=1\mod 2\\}$;

8 $\mathcal{Q}$.append$\left(R_{i}(S)\right)$;

9

10

11 $\ell\leftarrow\ell/2$;

12

13${\mathcal{T}}\leftarrow(n,c_{2}k/(\alpha-1),k,\alpha-1)$-SSuI;

14 foreach  _$T\in{\mathcal{T}}$_ do

15 $\mathcal{Q}$.append$(T)$;

16 for  _$i\leftarrow 1$ to $2\log_{2}n$_ do

17 $R_{i}(T)\leftarrow\\{v\in T\ :\ \lfloor v/2^{i-1}\rfloor=1\mod 2\\}$;

18 $\mathcal{Q}$.append$\left(R_{i}(T)\right)$;

19

20

return _$\mathcal{Q}$_

Algorithm 1 Construction of a sequence of queries solving Group Testing.

#### Decoding algorithm.

During the decoding algorithm we process, in subsequent iterations, the
feedbacks from enhanced selectors $\bar{{\mathcal{S}}}^{(\ell)}$ for
$\ell=k,k/2,k/4,\dots,c_{2}k/(\alpha-1)$. We will later prove, by induction,
that during processing $\bar{{\mathcal{S}}}^{(\ell)}$, $\ell/2$ new elements
from $K$ are decoded. To show this, we consider any iteration and let set
$K_{1}$ be the set of the elements that have been decoded in previous
iterations while set $K_{2}=K\setminus K_{1}$ be the set of unknown elements.
We treat $K_{1}$ as the interfering set and, by the properties of
${\mathcal{S}}^{(\ell)}$, we know that for at least $\ell/2$ elements $v$,
there exists a query $S\in{\mathcal{S}}^{(\ell)}$, such that $v\in S$,
$|K_{1}\cap S|<\alpha-1$, $|K_{2}\cap S|=1$. We observe that since we already
know the identifiers of all the elements from the interfering set $K_{1}$,
then using feedbacks from the additional queries ${\mathcal{R}}(S)$
(corresponding to balanced IDs) we can exactly decode the identifier of $v$.
We do this for all $\ell/2$ elements that are possible to decode in this
iteration and we proceed to the next iteration. After considering all
Selectors-under-Interference, we have only at most $c_{2}k/(\alpha-1)$ unknown
elements. To complete the decoding we use a Strong-Selector-under-
Interference, where the decoding procedure is exactly the same as in the case
of SuI (the interfering set is also the set of already decoded elements). The
properties of SSuI guarantee that we decode the identifiers of all the
remaining elements from $K$. See the pseudocode of decoding Algorithm 2 for
details).

Data: Feedback sequence.

Output: Set $K$

$\ell\leftarrow k,K_{acc}\leftarrow\emptyset$ ;

/* In set $K_{acc}$ we accumulate the decoded elements. */

1 while  _$\ell >\frac{c_{2}l}{\alpha-1}$_ do

/* We want to decode $l/2$ elements. */

2 for  _$i\leftarrow 1$ to $l/2$_ do

/* Look for queries in ${\mathcal{S}}^{(\ell)}$, for which we can decode a new
element. */

3 foreach  _$S\in{\mathcal{S}}^{(\ell)}$_ do

4 if  _$\mathsf{Result}(S) <\alpha-1$ and $|S\cap
K_{acc}|=\mathsf{Result}(S)-1$_ then

5 $K_{acc}\leftarrow K_{acc}\cup\\{DecodeElement(S,K_{acc})\\}$

6

7

8 $\ell\leftarrow\ell/2$;

9

/* Decode all the remaining elements. */

/* Iteratively find queries in ${\mathcal{T}}$, for which we can decode a new
element. */

10 foreach  _$T\in{\mathcal{T}}$_ do

11 if  _$\mathsf{Result}(T) <\alpha-1$ and $|T\cap
K_{acc}|=\mathsf{Result}(T)-1$_ then

12 $K_{acc}\leftarrow K_{acc}\cup\\{DecodeElement(T,K_{acc})\\}$

13

14return _$K_{acc}$_

1 Procedure  _DecodeElement( $Q$,$K_{acc}$)_

2 $v\leftarrow 0$;

3 for  _$j\leftarrow 2\log_{2}n$ downto $0$_ do

/* Take the feedback from set $R_{j}(Q)$. Calculate the feedback from set
$R_{j}(Q)$, if hidden set was exactly $K_{acc}$. The difference is the $j$-th
least significant bit of Balanced ID of the new element $v$. */

4 $v\leftarrow 2\cdot v$;

5 $v\leftarrow v+\mathsf{Result}(R_{j}(Q))-|R_{j}(Q)\cap K_{acc}|$

6 return _$v$_

Algorithm 2 Decoding of the elements.

######  Lemma 1.

There is an explicit polynomial-time algorithm constructing non-adaptive
queries $Q_{1},\ldots,Q_{m}$ and decoding any hidden set $K$ of size at most
$k\leq n$, from the feedback vector in polynomial time, under feedback
${\mathcal{F}}_{\alpha}$ and for $m=O((k/\alpha)^{2}\log^{3}n+k{\rm\ polylog\
}n)$ queries. Moreover, every element occurs in
$O(\frac{k}{\alpha}\log^{2}n+{\rm\ polylog\ }n)$ queries.

###### Proof.

We start from describing a procedure of revealing elements in any given set
$K$ of at most $k$ elements, together with a formal (inductive) argument of
its correctness. Our first goal is to show that by the beginning of
$\bar{{\mathcal{S}}}^{(\ell)}$, for $\ell$ stepping down from $k$ to
$c_{2}k/(\alpha-1)$, we have not learned about the identity of at most $\ell$
elements from the hidden set $K$.

The proof is by induction – it clearly holds in the beginning of the
computation, as the set $K$ has at most $\ell=k$ elements. We prove the
inductive step: by the end of $\bar{{\mathcal{S}}}^{(\ell)}$, at most $\ell/2$
elements are not learned. We set $K_{2}$ to be the set of learned elements and
$K_{1}=K\setminus K_{2}$. Clearly, $|K_{2}|\leq k$, and by the inductive
assumption $|K_{1}|\leq\ell\leq k$. For such $K_{1}$ and $K_{2}$, by the
definition of SuI, there are at most $\ell/2$ elements from $K_{1}$ that are
not occurring in some round without other such elements or with at least
$\alpha-1$ of already learned elements from $K_{2}$. Consider a previously not
learned element $v\in K_{1}$, for which there exists a good query in
$\bar{{\mathcal{S}}}^{(\ell)}$, i.e., a query
$S\in\bar{{\mathcal{S}}}^{(\ell)}$ such that $S\cap K_{1}=\\{v\\}$ and $|S\cap
K_{2}|<\alpha-1$. At this point of decoding of set $K$ we know the Balanced
IDs of all elements from set $K_{2}$. Hence we can calculate the
$2\log_{2}n$-bit feedback vector from sets $K_{2}\cap R_{1}(S),K_{2}\cap
R_{2}(S),\dots,K_{2}\cap R_{2\log_{2}n}(S)$. We compare this feedback vector
with the output of the enhanced selector, which is the feedback vector for
sets $K\cap R_{1}(S),K\cap R_{2}(S),\dots,K\cap R_{2\log_{2}n}(S)$. The
difference between the latter and the former is exactly the Balanced ID of
$v$. In case this difference does not form a Balanced ID of any element, i.e.,
it has some value bigger than $1$ or otherwise the number of 1’s is different
from $\log_{2}n$, or in case ${\mathcal{F}}_{\alpha}(K\cap S)=\alpha$ (recall
that $S$ is also in the constructed selector) the feedback from this
${\mathcal{R}}(S)$ is ignored. This is done to avoid misinterpreting the
feedback and false discovery of an element which is not in $K$. Indeed, first
note that the fact $|K\cap S|\geq\alpha$ will automatically discard the part
of the feedback from $K\cap R_{1}(S),K\cap R_{2}(S),\dots,K\cap
R_{2\log_{2}n}(S)$, as it indicates that the intersection is too large to
provide correct decoding of an element. Second, assuming $|K\cap S|<\alpha$,
if there are no elements in $K_{1}\cap S$ then the difference between
feedbacks gives vector of zeros, and if there will be at least two elements in
$K_{1}\cap S$, the difference between feedbacks will contain a value of at
least $2$ or all 1’s, as it will be a bitwise sum of at least two Balanced IDs
of $\log_{2}n$ ones each. By the definition of SuI we can find $l/2$ such
elements $v$. This shows that during decoding of enhanced
$\bar{{\mathcal{S}}}^{(\ell)}$ we learn the identities of $\ell/2$ new
elements. This completes the inductive proof. Note here that the inductive
step, being one of $O(\log n)$ steps, defines a polynomial time algorithm
decoding some elements one-by-one – indeed, it computes two feedbacks of
polynomial number of queries, computes the difference and deducts based on the
structure of subsequent blocks of $O(\log n)$ size.

The above analysis implies, that before applying
$(n,c_{2}k/(\alpha-1),k,\alpha-1)$-SSuI we have not discovered at most
$c_{2}k/(\alpha-1)$ elements. Thus, by definition,
$(n,c_{2}k/(\alpha-1),k,\alpha-1)$-SSuI combined with Balanced IDs reveals all
the remaining elements in the same way as the SuI’s above – the only
difference in the argument is that instead of leaving at most $\ell/2$
undiscovered elements in the $\ell$-th inductive step, due to the nature of
SuI’s, the SSuI guarantees that every undiscovered element will occur in a
good query. The same argument as for SuI’s proves that the decoding algorithm
defined this way works in polynomial time.

By Theorem 4 below, the length of $(n,\ell,1/2,k,\alpha)$-SuI is
$O(\min\left\\{n,\ell{\rm\ polylog\ }n\right\\})$, which sums up to
$O(\min\left\\{n,k{\rm\ polylog\ }n\right\\})$, and is multiplied by
$\Theta(\log n)$ due to amplification by Balanced IDs. By Theorem 6, the
length of $(n,c_{2}k/\alpha,k,\alpha)$-SSuI is $O((k/\alpha)^{2}\log^{2}n)$,
and it is also increased by factor $\Theta(\log n)$ due to Balanced IDs. If we
apply the above reasoning with respect to the number of queries containing an
element, we get that every element occurs in
$O(\frac{k}{\alpha}\log^{2}n+{\rm\ polylog\ }n)$ queries. ∎

#### Implementing $\alpha$-Round-Robin for large values of $k/\alpha$

The question arises from the previous result if one could efficiently
construct a shorter sequence of queries if $(k/\alpha)^{2}>n/\alpha$? In the
case of full feedback (i.e., $\alpha=k$) the common way to deal with large
values of $k$ is via Round-Robin, which means that queries are singletons and
consequently, the length of such query sequence is $n$. This also works for an
arbitrary value of $\alpha\leq k$, however the lower bound in Theorem 2 and
the existential upper bound in Theorem 3 suggest that in such case there could
exist a shorter query system of length $O((k+(n/\alpha)){\rm\ polylog\ }n)$.
Indeed, if we modify our construction in such case, we could obtain such a
goal. Namely, we concatenate:

  * •

selectors $\bar{{\mathcal{S}}}^{(\ell)}$, for $\ell$ being a power of $2$
starting from the largest $\ell=k$ and finishing at
$\ell=2c_{2}\kappa/\alpha$; followed by

  * •

selectors $\bar{{\mathcal{S}}}|_{\alpha}^{(\ell)}$, for $\ell$ being a power
of $2$ starting from the largest $\ell=c_{2}\kappa/\alpha$ and finishing with
$\ell=1$.

Then we enhance them based on Balanced IDs, as in the previous construction.
Then, applying Theorem 4 for concatenated $\bar{{\mathcal{S}}}^{(\ell)}$ and
Theorem 5 for concatenated $\bar{{\mathcal{S}}}|_{\alpha}^{(\ell)}$, instead
of combination of Theorems 4 and 6 as it was in the proof of Lemma 1 with
respect to $\bar{{\mathcal{S}}}^{(\ell)}$, we get the following result.

######  Lemma 2.

There is an explicit polynomial-time algorithm constructing non-adaptive
queries $Q_{1},\ldots,Q_{m}$ and decoding any hidden set $K$ of size at most
$k\leq n$, from the feedback vector in polynomial time, under feedback
${\mathcal{F}}_{\alpha}$ and for $m=O((k+n/\alpha){\rm\ polylog\ }n)$ queries.
Moreover, each element occurs in $O({\rm\ polylog\ }n)$ queries.

###### Proof.

The proof is analogous to the proof of Lemma 1, except that we continue
proving the invariant until $\ell=2c_{2}\kappa/\alpha$, using same properties
guaranteed by Theorems 4, and continue the invariant until $\ell=1$, using
SuI’s of slightly different length formula from Theorem 5. The correctness
argument, as well as polynomial-time query construction and decoding of the
elements, are the same as in the invariant proof in Lemma 1. Then, by Theorem
4 for concatenated $\bar{{\mathcal{S}}}^{(\ell)}$ and by Theorem 5 for
concatenated $\bar{{\mathcal{S}}}|_{\alpha}^{(\ell)}$, we argue that the total
length of the obtained sequence is $m=O((k+n/\alpha){\rm\ polylog\ }n)$.
Indeed, the first part results from the telescoping sum for different $\ell$
and the second component is a logarithmic amplification of the original
$O((n/\alpha){\rm\ polylog\ }n)$ length of SuI’s; all is amplified by $O(\log
n)$ due to enhancement of the used SuI’s by Balanced IDs. In all the
components, every element belongs to $O({\rm\ polylog\ }n)$ queries, by
Theorems 4 and 5, in the final sequence it also occurs in $O({\rm\ polylog\
}n)$ queries. ∎

Combining Lemma 1 with Lemma 2 gives Theorem 1. Note that in both lemmas the
decoding algorithm proceeds query-by-query, each time spending polylogarithmic
time on each of them; additionally, for each decoded element, an update of the
feedback of next queries needs to be done, which takes time proportional to
the number of occurrences of the discovered element in the queries. Thus, it
is asymptotically upper bounded by the length of the sequence plus $k$ times
the upper bound on the number of occurrences of an element in the queries
(polylogarithmic).

##  5 Applications

#### Group testing on multi-sets.

Assume instead of a hidden set, there is a hidden multi-set $K$, containing at
most $k$ elements from $[N]$. Multi-set means that each element may have
several multiplicities. Let $\kappa$ be the sum of multiplicities of elements
in $K$, and we assume it is unknown to the algorithm. We could decode all
elements in $K$ with their multiplicities using similar approach as in Section
4, with the following modifications.

First, we need to have a sufficiently large cap $\alpha$ to decode each
multiplicity, i.e., $\alpha$ should be not smaller than $\kappa$.

Second, in the construction Algorithm 1, instead of applying SuI’s only while
$\ell>\frac{c_{2}l}{\alpha-1}$ (line 2) and then SSuI (line 10), we need to
keep applying SuI’s while $\ell>1$ (line 2) and remove line 10. Analogously in
the structure of decoding Algorithm 2 – updating line 2 and removing the end
starting from line 8. This is because the multiplicities of elements not
decoded by SuI’s in the While-loop could still be larger than $\sqrt{\kappa}$,
therefore switching to SSuI may not be enough to decode their multipicities
(note that $\kappa$ plays in this part a similar role to $k$ in the original
algorithm for sets without multiplicities). The correctness still holds, as
each consecutive SuI combined with balanced IDs reveals full multiplicities of
a fraction of remaining elements in $K$ (instead of just presence of elements,
as in the original proof of Theorem 1). The asymptotic query complexity
(codeword length) stays the same as the part coming from the While-loop (the
sum of SuI lengths multiplied by $2\log n$ coming from balanced IDs), since we
just add a negligible tail in the sum of lengths of SuI’s considered in
Theorem 1.

Third, polynomial time is now with respect to $n$ and $\log\kappa$, to deal
with multiplicities.

Therefore we get:

######  Theorem 7.

There is an explicit polynomial-time (in $n$ and $\log\kappa$) algorithm
constructing non-adaptive queries $Q_{1},\ldots,Q_{m}$, for
$m=O\left(\min\left\\{n,k{\rm\ polylog\ }n\right\\}\right)$, that correctly
decode a multi-set $K$ of at most $k$ elements and multiplicity $\kappa$
(where $k$ is known but $\kappa$ could be unknown) under feedback
${\mathcal{F}}_{\alpha}$ with polynomial-time (in $n$ and $\log\kappa$)
decoding, where $\alpha$ is not smaller than the largest multiplicity of an
element in $K$. Moreover, every element occurs in $O({\rm\ polylog\ }n)$
queries, and the decoding time is $O(m+k{\rm\ polylog\ }n)$.

#### Maintaining and reconstructing a (multi) set.

Consider the following problem. We have an incoming very large stream of
insertion or deletions of elements from some domain $N$. The objective is to
propose a datastructure that processes such operations and at any step (i.e.,
after processing a certain number of operations) it can answer a request and
provide information about the set specified by the operations that have been
processes so far. This is a commonly studied setting (see e.g., [16, 37]) and
extracting information from such stream of operations has applications to
database systems. Our algorithms lead directly to an explicit formulation of a
datastructure capable of extracting the whole (multi) set, however only
conditioned that (at the moment of the request) the sum of multiplicities of
the hidden set does not exceed $k$. The space complexity of the datastructure
would equal to the number of queries of the algorithm, which is
$O\left(\min\left\\{n,k{\rm\ polylog\ }n\right\\}\right)$.

#### Maintaining and reconstructing a graph with dynamically added or removed
edges.

Consider a graph $G$ with a fixed set of nodes and an online stream of
operations on $G$, where a single operation could be either adding or removing
an edge to/from $G$. Assume for the ease of presentation that after each
operation, the maximum node degree is bounded by some parameter $k$. 111This
assumption could be waved by using Group Testing codes for different
parameters $k$, depending on the actual size of $G$, hence $k$ could play role
of an average size of a neighborhood. Consider a sequence of queries from
Theorem 1 on the set of all possible $\frac{n(n-1)}{2}$ edges. For each
added/removed edge, we increase/decrease (resp.) a counter associated with
each query containing this edge. As each edge occurs in
$O(\frac{k}{\alpha}\log^{2}n+{\rm\ polylog\ }n)$ queries, and thus this is an
upper bound (up to some additional logarithmic factor) on the time of each
graph update, which is polylogarithmic for $\alpha$ close to $k$. Whenever one
would like to recover the whole graph, a reconstruction algorithm is applied,
which takes $O(m+\frac{k^{2}}{\alpha}\log^{2}n+k{\rm\ polylog\ }n)$ steps,
which for $\alpha$ close to $k$ is $O(nk{\rm\ polylog\ }n)$. Note that the
latter formula corresponds to (the upper bound on) the number of edges in $G$.
To summarize, we implemented graph updates operations in ${\rm\ polylog\ }n$
time per (edge-)operation, and the whole graph recovery in time proportional
to the graph size (number of edges) times ${\rm\ polylog\ }n$.

#### Private Parallel Information Retrieval (PPIR)

One of techniques to speed-up Information Retrieval from a large dataset is to
employ autonomous agents searching parts of the datasets, c.f., [27]. Our
Capped Quantitative Group Testing algorithms could be applied to achieve this
goal, additionally providing a level of privacy. Assume that there are
$m=O(k{\rm\ polylog\ }n)$ simple autonomous agents, where $m$ is the number of
queries in our Capped QGT system. Each agent $i$ is capable to search only
through records captured by the corresponding query set $Q_{i}$, and only
count the number of occurrences of records satisfying the search criteria, but
only up to $\sqrt{k}$. If all agents share privately their results with the
user, he can decompose the set $K$ of at most $k$ elements satisfying the
searching criteria, while each of the agents has knowledge about at most
$\sqrt{k}$ of these elements. It follows from the construction of our queries
that each of them is of size $O(n/\sqrt{k}{\rm\ polylog\ }n)$, which is worst-
case number of records that a single agent needs to check – thus equal to
parallel time. Note also that agents perform very simple counting operations,
thus the PPIR algorithm could be efficient in practice.

##  6 Constructions of combinatorial tools

###  6.1 Polynomial-time construction of Selectors-under-Interference

In this section, we show how to construct, in time polynomial in $n$, an
$(n,\ell,\epsilon,\kappa,\alpha)$-SuI $\mathcal{S}$ of size
$O(\min\left\\{n,\ell{\rm\ polylog\ }n\right\\})$, for any integer parameters
$\ell,\kappa\leq n$, $\alpha\leq\kappa$, and any (arbitrarily small) constant
$\epsilon\in(0,1/2)$. Let $\ell^{*}$ denote $\ell\varepsilon$. The
construction combines dispersers with strong selectors, see also the
pseudocode Algorithm 3. We start from specifying those tools.

##### Disperser.

Consider a bipartite graph $G=(V,W,E)$, where $|V|=n$, which is an
$(\ell^{*},d,\varepsilon)$-disperser with entropy loss $\delta$, i.e., it has
left-degree $d$, $|W|=\Theta(\ell^{*}d/\delta)$, and satisfies the following
dispersion condition: for each $L\subseteq V$ such that $|L|\geq\ell^{*}$, the
set $N_{G}(L)$ of neighbors of $L$ in graph $G$ is of size at least
$(1-\varepsilon)|W|$. Note that it is enough for us to take as $\epsilon$ in
the dispersion property the same value as in the constructed
$(n,\ell,\epsilon,\kappa,\alpha)$-SuI $\mathcal{S}$. An explicit construction
(i.e., in time polynomial in $n$) of dispersers was given by Ta-Shma, Umans
and Zuckerman [46], for any $n\geq\ell$, and some $\delta=O(\log^{3}n)$, where
$d=O(\text{polylog }n)$.

##### Strong selector.

Let ${\mathcal{T}}=\\{T_{1},\ldots,T_{m}\\}$ be an explicit
$(n,c\delta)$-strong-selector (also called strongly-selective family), for a
sufficiently large constant $c>0$ that will be fixed later, of size
$m=O(\min\\{n,\delta^{2}\log^{2}n\\})$, as constructed by Kautz and Singleton
[41].

##### Construction of $(n,\ell,\epsilon,\kappa,\alpha)$-SuI $\mathcal{S}$.

We define an $(n,\ell,\epsilon,\kappa,\alpha)$-SuI $\mathcal{S}$ of size
$\min\\{n,m|W|\\}$, which consists of sets $S_{i}$, for $1\leq
i\leq\min\\{n,m|W|\\}$. There are two cases to consider, depending on the
relation between $n$ and $m|W|$. The case of $n\leq m|W|$ is simple: take the
singleton containing only the $i$-th element of $V$ as $S_{i}$. Consider a
more interesting case when $n>m|W|$. For $i=am+b\leq m|W|$, where $a$ and $b$
are non-negative integers satisfying $a+b>0$, let $S_{i}$ contain all the
nodes $v\in V$ such that $v$ is a neighbor of the $a$-th node in $W$ and $v\in
T_{b}$.

Data: $(\ell\epsilon,d,\varepsilon)$-disperser $G=(V,W,E)$,
$V=\\{v_{1},\dots,v_{n}\\}$, $W=\\{w_{1},\dots,w_{|W|}\\}$, $|W|=\Theta(\ell
d/\delta)$, $\delta=O(\log^{3}n)$, $d=O(\text{polylog }n)$,

$(n,c\delta)$-strong-selector ${\mathcal{T}}=\\{T_{1},\ldots,T_{m}\\}$

Result: $(n,\ell,\epsilon,\kappa,\alpha)$-SuI $\mathcal{S}$

1 for  _$i\leftarrow 1$ to $\min\\{n,m|W|\\}$_ do

2 if  _$n >m|W|$_ then

3 $S_{i}\leftarrow\\{v_{i}\\}$

4 else

5 Find $a,b>0$, such that $i=am+b\leq m|W|$ ;

6 $S_{i}\leftarrow T_{b}\cap N_{G}(w_{a})$

7

return _$\langle S_{1},S_{2},\dots,S_{\min\\{n,m|W|\\}}\rangle$_

Algorithm 3 Construction of Selectors-under-Interference (SuI).

###### Proof of Theorem 4.

First we show that the constructed ${\mathcal{S}}$ is an
$(n,\ell,\epsilon,\kappa,\alpha)$-SuI. The case $n\leq m|W|$ is clear, since
each element in a set $K_{1}$ of size at most $\ell$ occurs as a singleton in
some set $S_{i}$ (here it does not matter what the set $K_{2}$ is).

Consider the case $n>m|W|$. Let a set $K_{1}\subseteq V$ be of size at most
$\ell$ and a set $K_{2}$ of at most $\kappa$ elements. Suppose, to the
contrary, that there is a set $L\subseteq K_{1}$ of size $\ell^{*}$ such that
none among the elements in $L$ is $K_{1}$-selected by ${\mathcal{S}}$ under
$\alpha$-interference from $K_{2}$, that is, $S_{i}\cap L\neq\\{v\\}$ or
$|S_{i}\cap K_{2}|\geq\alpha$, for any $v\in L$ and $1\leq i\leq m|W|$.
(Recall that $\ell^{*}=\ell\varepsilon$.)

Claim: Every $w\in N_{G}(L)$ has more than $c\delta$ neighbors in $K_{1}$ or
at least $\alpha$ neighbors in $K_{2}$.

The proof is by contradiction. Suppose, to the contrary, that there is $w\in
N_{G}(L)$ which has at most $c\delta$ neighbors in $K_{1}$ and less than
$\alpha$ neighbors in $K_{2}$, that is, $|N_{G}(w)\cap K_{1}|\leq c\delta$ and
$|N_{G}(w)\cap K_{2}|<\alpha$. By the former property and the fact that
${\mathcal{T}}$ is an $(n,c\delta)$-strong-selector, we get that, for every
$v\in N_{G}(w)\cap K_{1}$, the equalities

$S_{w\cdot m+b}\cap K_{1}=(T_{b}\cap N_{G}(w))\cap
K_{1}=T_{b}\cap(N_{G}(w)\cap K_{1})=\\{v\\}$

hold, for some $1\leq b\leq m$. This holds in particular for every $v\in L\cap
N_{G}(w)\cap K_{1}$. There is at least one such $v\in L\cap N_{G}(w)\cap
K_{1}$ because set $L\cap N_{G}(w)\cap K_{1}$ is nonempty since $w\in
N_{G}(L)$ and $L\subseteq K_{1}$. Additionally, recall that $N_{G}(w)\cap
K_{2}$ is smaller than $\alpha$. The existence of such $v$ is in contradiction
with the choice of $L$. Namely, $L$ contains only elements which are not
$K_{1}$-selected by sets from ${\mathcal{S}}$ under $\alpha$-interference from
$K_{2}$, but $v\in L\cap N_{G}(w)\cap K_{1}$ is selected from $K_{1}$ by some
set $S_{w\cdot m+b}$ and the interference from $K_{2}$ on this set is smaller
than $\alpha$. This makes the proof of Claim complete. $\blacksquare$

Recall that $|L|=\ell^{*}=\ell\varepsilon$. By dispersion, the set $N_{G}(L)$
is of size larger than $(1-\varepsilon)|W|$. Consider two cases below – they
cover all possible cases because of the above Claim.

Case 1: At least half of the nodes $w$ in $N_{G}(L)$ have more than $c\delta$
neighbors in $K_{1}$.

In this case, the total number of edges between the nodes in $K_{1}$ and
$N_{G}(L)$ in graph $G$ is larger than

$\frac{1}{2}(1-\varepsilon)|W|\cdot
c\delta=\frac{1}{2}(1-\varepsilon)\Theta(\ell d/\delta)\cdot c\delta>\ell d\
,$

for a sufficiently large constant $c$. This is a contradiction, since the
total number of edges in graph $G$ incident to nodes in $K_{1}$ is at most
$|K_{1}|d=\ell d$.

Case 2: More than half of the nodes $w$ in $N_{G}(L)$ have at least $\alpha$
neighbors in $K_{2}$.

In this case, the total number of edges between the nodes in $K_{2}$ and
$N_{G}(L)$ in graph $G$ is larger than

$\frac{1}{2}(1-\varepsilon)|W|\cdot\alpha=\frac{1}{2}(1-\varepsilon)\Theta(\ell
d/\delta)\cdot\alpha>\kappa d\ ,$

for a sufficiently large constant $c_{2}$. This is a contradiction, since the
total number of edges in graph $G$ incident to nodes in $K_{2}$ is at most
$|K_{2}|d=\kappa d$.

Thus, it follows from the contradictions in both cases that ${\mathcal{S}}$ is
an $(n,\ell,\epsilon,\kappa,\alpha)$-SuI.

The size of this selector is

$\displaystyle\min\\{n,m|W|\\}$ $\displaystyle=$ $\displaystyle
O\left(\min\left\\{n,\delta^{2}\log^{2}n\cdot\ell^{*}d/\delta\right\\}\right)$
$\displaystyle=$ $\displaystyle O\left(\min\left\\{n,\ell^{*}\delta
d\log^{2}n\right\\}\right)$ $\displaystyle=$ $\displaystyle
O\left(\min\left\\{n,\ell{\rm\ polylog\ }n\right\\}\right)\ ,$

since $d=O({\rm\ polylog\ }n)$, $\delta=O(\log^{3}n)$ and
$\ell=\Theta(\ell^{*})$. It follows directly from the construction that each
element is in $O(d\delta^{2}\log^{2}n)=O({\rm\ polylog\ }n)$ queries. ∎

#### Sparser SuI for small $\ell$ compared to $\kappa/\alpha$

What if $\alpha\ell\leq c_{2}\kappa$ for some constant $c_{2}>0$? We could
modify the above construction as follows. Let
$\gamma=\frac{\alpha\ell}{\kappa}$. If $\gamma\leq c_{2}$, we take the
$(n,c_{2}\kappa/\alpha,\epsilon,\kappa,\alpha)$-SuI ${\mathcal{S}}$ from
Theorem 4 and partition each set $S_{i}\in{\mathcal{S}}$ into the smallest
number of sets of size at most $\alpha$ each. Note that the total number of
occurrences of elements in sets $S_{i}\in{\mathcal{S}}$ in the above
construction is upper bounded by the number of edges in the disperser
multiplied by the number of occurrences of elements in the strong selector,
which asymptotically gives $O(nd\cdot\delta\log n)=O(n{\rm\ polylog\ }n)$.
Therefore, after the above partition of sets $S_{i}$, the total number of sets
in the obtained sequence is $O\left(\min\left\\{n,(\kappa/\alpha){\rm\
polylog\ }n\right\\}+\frac{n}{\alpha}{\rm\ polylog\ }n\right)$. We denote the
new sequence obtained from ${\mathcal{S}}$ by ${\mathcal{S}}|_{\alpha}$ Note
that it is an $(n,\ell,\epsilon,\kappa,\alpha)$-SuI, as if in the original
$(n,c_{2}\kappa/\alpha,\epsilon,\kappa,\alpha)$-SuI ${\mathcal{S}}$ an element
$v$ was $\alpha$-selected from a set $K_{1}$ under interference from $K_{2}$,
where $|K_{1}|\leq\ell\leq c_{2}\kappa/\alpha$, it occurs in some of the new
sets being in the partition of the original selecting set, and by monotonicity
of selection – $v$ is also $\alpha$ selected from $K_{1}$ under interference
from $K_{2}$. Note that in the above decoding, the number of queries
containing any element remains $O({\rm\ polylog\ }n)$ as in original SuI from
Theorem 4. Hence, by taking the construction of family
${\mathcal{S}}|_{\alpha}$, we proved Theorem 5.

###  6.2 Polynomial-time construction of Strong-Selectors-under-Interference

In order to construct an $(n,\ell,\kappa,\alpha)$-SSuI $\mathcal{S}$, we use
the following variation of a Reed-Solomon superimposed code, analogous to the
construction used in [41], however here we prove an additional property of
these objects.

  1. 1.

Let $d=\left\lceil\log_{\ell}n\right\rceil$ and $q=c\cdot\ell\cdot d$ for some
constant $c>0$ such that $q^{d+1}\geq n$ and $q$ is prime.

  2. 2.

Consider all polynomials of degree $d$ over field ${\mathbb{F}}_{q}$; there
are $q^{d+1}$ such polynomials. Remove $q^{d+1}-n$ arbitrary polynomials and
denote the remaining polynomials by $P_{1},P_{2},\dots,P_{n}$.

  3. 3.

Create the following matrix $M$ of size $q\times n$. Each column $i$, for
$1\leq i\leq n$, stores values $P_{i}(x)$ of polynomial $P_{i}$ for arguments
$x=0,1,\dots,q-1$; the arguments correspond to rows of $M$. Next, matrix
$M^{*}$ is created from $M$ as follows: each value
$y=P_{i}(x)\in\\{0,1,\ldots,q-1\\}$ is represented and padded in $q$
consecutive rows containing $0$s and $1$s, where $1$ is exactly in $y+1$-st
padded row, while in all other padded rows there are $0$s. Notice that each
column of $M^{*}$ has $q^{2}$ rows ($q$ rows per each argument), therefore
$M^{*}$ is of size $q^{2}\times n$.

  4. 4.

Set $T_{i}\subseteq[n]$, for $1\leq i\leq q^{2}$, is defined based on row $i$
of matrix $M^{*}$: it contains all elements $v\in[n]$ such that
$M^{*}[j,v]=1$. (Recall that each such $v$ corresponds to some polynomial.)
For a fixed constant $c>0$, $\\{T_{i}\\}_{i=1}^{q^{2}}$ forms a family
$\mathcal{T}^{(c)}$ of subsets of set $\\{1,\ldots,n\\}$.

The above construction could be presented as a simplified pseudocode as
follows:

1 $d\leftarrow\left\lceil\log_{\ell}n\right\rceil$;

2 $q\leftarrow c\cdot\ell\cdot d$ for some constant $c>0$ such that
$q^{d+1}\geq n$ and $q$ is prime;

/* There are $q^{d+1}\geq n$ such polynomials. */

3 $P_{1},P_{2},\dots,P_{n}\leftarrow$ arbitrary $n$ polynomials of degree $d$
over field ${\mathbb{F}}_{q}$;

4 $\mathcal{T}^{(c)}\leftarrow$ sequence of $q^{2}$ empty sets
$\\{T_{i}\\}_{i=1}^{q^{2}}$;

5 for  _$i\leftarrow 1$ to _$n$__ do

6 for  _$x\leftarrow 0$ to _$q-1$__ do

/* Value of $i$-th polynomial for argument $x$. */

7 $value\leftarrow P_{i}(x)$;

/* Encode $value$ in unary on positions $x\cdot q+1,x\cdot q+2,\dots(x+1)\cdot
q$ */

8 $index\leftarrow x\cdot q+value+1$;

/* Add element $i$ to the corresponding set $T$. */

9 $T_{index}$.add$(i)$

10

return _$\mathcal{T}^{(c)}$_

Algorithm 4 Construction of Strong-Selectors-under-Interference

###### Proof of Theorem 6.

Consider the constructed family $\mathcal{T}^{(c)}$. Polynomial time of this
construction follows directly from the fact that the space of polynomials over
field $[q]$ is of polynomial size in $n$ and all the operations on them are
polynomial. The length follows from the fact that it is
$q^{2}=O(\ell^{2}\log_{\ell}^{2}n)$.

Recall that each element $v\in[n]$ correspond to some polynomial of degree at
most $d$ over ${\mathbb{F}}_{q}$. Note that two polynomials $P_{i}$ and
$P_{j}$ of degree $d$ with $i\neq j$, can have equal values for at most $d$
different arguments. This is because they have equal values for arguments $x$
for which $P_{i}(x)-P_{j}(x)=0$. However, $P_{i}-P_{j}$ is a polynomial of
degree at most $d$, so it can have at most $d$ zeroes. Hence,
$P_{i}(x)=P_{j}(x)$ for at most $d$ different arguments $x$.

Take any polynomial $P_{i}$ and any other at most $\ell-1$ polynomials
$P_{j}$, which altogether form set $K_{1}$ of at most $\ell$ polynomials.
There are at most $(\ell-1)\cdot d$ different arguments where one of the other
$\ell-1$ polynomials can be equal to $P_{i}$. Hence, for at least
$q-(\ell-1)\cdot d$ different arguments, the values of the polynomial $P_{i}$
are different than the values of the other polynomials in $K_{1}$. Let us call
the set of these arguments $A$.

Consider any set $K_{2}\subseteq[n]$ of at most $\kappa$ elements
(corresponding to polynomials). Consider arguments from set $A$ for which
$P_{i}$ has the same value as at least $\alpha$ other polynomials in $K_{2}$.
The number of such arguments is at most

$\frac{\kappa\cdot d}{\alpha}\leq(\ell/c_{2})\cdot d<(c-1)\ell\cdot
d<q-(\ell-1)\cdot d\ ,$

which means it is smaller than $|A|$ for sufficiently large constant $c>0$ in
the definition of $q=c\ell\cdot d$. Therefore, there is an argument (in set
$A$) such that the value of $P_{i}$ is different from the values of all other
$\ell-1$ polynomials in $K_{1}$ and less than $\alpha$ polynomials in set
$K_{2}$. As this holds for an arbitrary polynomial $P_{i}$ in an arbitrary set
$K_{1}$ of at most $\ell$ polynomials (in total) and an arbitrary set $K_{2}$
of at most $\kappa$ polynomials, ${\mathcal{T}}^{(c)}$ is an
$(n,\ell,\kappa,\alpha)$-SSuI. Finally, it follows directly from the
construction that every element occurs in $q=O(\ell\log_{\ell}n)$ queries. ∎

##  7 Lower bound

###### Proof of Theorem 2.

We will first show the
$\min\left\\{\frac{n}{\alpha},\frac{k^{2}}{\alpha^{2}}\right\\}$ component.
Assume that a sequence of queries $Q_{1},Q_{2},\dots,Q_{t}$ of length $t$
solves Group Testing. We want to show the lower bound that holds for any
feedback function capped at $\alpha$ hence we assume that the feedback
function $\mathcal{F}$ returns the whole set (i.e., the identifiers of all the
elements). Recall that $\mathcal{F}$ works only for sets with at most $\alpha$
elements. We begin by proving the following:
Claim A: For any set $K$, with $|K|\leq k$ and any $x\in K$, there must exist
$\tau\in\\{1,2,\dots,t\\}$, such that $x\in Q_{\tau}$ and $|K\cap
Q_{\tau}|\leq\alpha+1$.

The proof is by contradiction. Assume that such a set $K^{*}$ and element
$x^{*}$ exist for which there is no such query. Consider feedback vectors for
sets $K^{*}$ and $K^{*}\setminus\\{x^{*}\\}$. For any query that does not
contain $x^{*}$, the feedback is clearly identical. For any query $Q_{\tau}$,
such that $x^{*}\in Q_{\tau}$, we have $|Q_{\tau}\cap K^{*}|\geq\alpha+2$ and
$|Q_{\tau}\cap(K^{*}\setminus\\{x^{*}\\})|\geq\alpha+1$ and sets $K^{*}$ and
$K^{*}\setminus\\{x^{*}\\}$ are indistinguishable under any feedback capped at
$\alpha$ hence the sequence of queries does not solve the problem. This
completes the proof of Claim A. $\blacksquare$

Take all queries that have at most $\alpha+1$ elements and all elements that
belong to such queries. We have: $N_{s}=\bigcup_{\tau\in\\{1,2,\dots,t\\}\\\
|Q_{\tau}|\leq\alpha+1}Q_{\tau}\ .$ Denote the remaining elements by
$N_{l}=N\setminus N_{s}$. We will consider two cases:
Case $1$: $|N_{s}|\geq n/2$

Observe that:
$t\geq|\\{\tau\in\\{1,2,\dots,t\\}:|Q_{\tau}|\leq\alpha+1\\}|\geq\frac{N_{s}}{\alpha+1}\geq\frac{n}{2(\alpha+1)}$.

Case $2$: $|N_{l}|\geq n/2$

In this case, we take an arbitrary subset $K_{1}$ of $k/2$ elements from
$N_{l}$. For every element $x\in K_{1}$, we consider a set of queries
$Q(x)=\\{Q_{\tau}\in\\{Q_{1},Q_{2},\dots,Q_{t}\\}:x\in Q_{\tau},|Q_{\tau}\cap
K_{1}|\leq\alpha+1\\}$. We first show the following:
Claim B: For every $x\in K_{1}$, we have $|Q(x)|\geq\frac{k}{2(\alpha+2)}$.

The proof is by contradiction. Assume that for some $x^{*}\in K_{1}$ we have
$|Q(x^{*})|<\frac{k}{2(\alpha+2)}$. Then, for every query $Q\in Q(x^{*})$, we
take $\alpha+2-|Q\cap K_{1}|$ elements from $Q\setminus K_{1}$. Such elements
exist since $|Q|\geq\alpha+2$. Choose such elements for each query in
$Q(x^{*})$ and gather them in set $K_{2}$. Note that since
$|Q(x^{*})|<\frac{k}{2(\alpha+2)}$, then $|K_{2}|\leq k/2$. Now observe that
set $K_{1}\cup K_{2}$ and element $x^{*}$ violate Claim A. The obtained
contradiction completes the proof of Claim B. $\blacksquare$

Now observe that each query belongs to at most $\alpha+1$ sets $Q(x)$ for
different values of $x\in K_{1}$. Thus: $t\geq\frac{\sum_{x\in
K_{1}}|Q(x)|}{\alpha+1}\geq\frac{k^{2}}{4(\alpha+1)(\alpha+2)}$.

To complete the proof observe that any algorithm must fall either into Case 1
or Case 2, hence any algorithm needs to use
$\Omega\left(\min\left\\{\frac{n}{\alpha},\frac{k^{2}}{\alpha^{2}}\right\\}\right)$
queries.

To see that any algorithm in ${\mathcal{F}}_{\alpha}$ feedback model at least
$k\frac{\log\frac{n}{k}}{\log\alpha}$ queries, observe that the feedback
vector must be unique for each set $K$ with at most $k$ elements. Hence we
need at least ${n\choose k}$ different feedback vectors for different sets.
Feedback has at most $\alpha$ values hence we get $\alpha^{t}\geq{n\choose k}$
and $t\in\Omega(k\frac{\log\frac{n}{k}}{\log\alpha})$. ∎

##  8 Existential upper bound

###### Proof of Theorem 3.

Assume that $\alpha>2\log_{2}n$, the opposite case will be considered at the
end of the proof. We will prove using the probabilistic method that a
$\alpha$-Round-Robin sequence of queries of length $t=O((n/\alpha+k)\log n)$
exists. We take
$t_{1}=\left\lceil\left(\frac{8n}{\alpha}\right)(\ln(ne)+4)\right\rceil$,
$t_{2}=\left\lceil k(\ln(ne)+4)\right\rceil$, $t=t_{1}+t_{2}$ and construct a
sequence of queries $\mathcal{Q}=\langle Q_{1},Q_{2},\dots,Q_{t}\rangle$ as
follows. For $i\in[1,t_{1}]$, Each query $Q_{i}$ is constructed by including
each element from $N$ independently at random with probability
$p=\frac{\alpha}{6n}$. For $i\in[t_{1}+1,t_{1}+t_{2}]$, each query $Q_{i}$ is
constructed by including each element from $N$ independently at random with
probability $p=\min\\{\frac{1}{6k},\frac{\alpha}{6n}\\}$. Denote the first
$t_{1}$ queries by $\mathcal{Q}_{1}$ and the remaining queries by
$\mathcal{Q}_{2}$.

Claim 1: With probability at least $2/3$ each query in $\mathcal{Q}$ has at
most $\alpha$ elements.

Take any query $Q\in\mathcal{Q}$ and observe that the size of the query is a
sum of Bernoulli trials and $E{|Q|}\leq\alpha/6$. Using Chernoff bound [23],
since $\alpha>6E{|Q|}$ we get: $\mathbb{P}\left[\,|Q|\geq\alpha\,\right]\leq
2^{-\alpha}\leq\frac{1}{n^{2}}\ .$ Hence, knowing that $\alpha>2\log_{2}n$ the
probability that any query is larger than $\alpha$ is by the union bound at
most $t/n^{2}<1/3$.

Claim 2: With probability at least $3/4$, for any set $K$, with $|K|\leq k$,
for $k\leq n/\alpha$, some query $Q\in\mathcal{Q}_{1}$, satisfies $|Q\cap
K|=1$.

Consider any query $Q\in\mathcal{Q}_{1}$ and set $K$. Let $k^{*}=|K|$. We know
that $k^{*}\leq n/\alpha$. We have:

$\mathbb{P}\left[\,|Q\cap
K|=1\,\right]=k^{*}\cdot\frac{\alpha}{6n}\cdot\left(1-\frac{\alpha}{6n}\right)^{k^{*}-1}\geq\frac{k^{*}\alpha}{6n}\cdot\left(1-\frac{k^{*}\alpha}{6n}\right)\geq\frac{k^{*}\alpha}{8n}\
.$

Hence if $k^{*}\in[2^{i},2^{i+1}]$, then $\mathbb{P}\left[\,|Q\cap
K|=1\,\right]\geq\frac{2^{i}\alpha}{8n}$. We want to union bound the
probability that the sequence fails to select some element from set $K$ over
all possible sets $K$. We denote event $\mathsf{fail}$ as the event that
$\mathcal{Q}_{1}$ fails to hit any set with a most $k$ elements. The possible
number of sets of $K$ with $k^{*}\in[2^{i},2^{i+1}]$ is at most
$2^{i+1}{n\choose 2^{i+1}}$. Thus:

$\mathbb{P}\left[\,\mathsf{fail}\,\right]\leq\sum_{i=0}^{\log
k}2^{i+1}{n\choose
2^{i+1}}\left(1-\frac{2^{i}\alpha}{8n}\right)^{t_{1}}\leq\sum_{i=0}^{\log
k}e^{i+1}\cdot
e^{2^{i}\ln\frac{ne}{2^{i}}}e^{-t_{1}\cdot\frac{2^{i}\alpha}{8n}}\ .$

Knowing that $t_{1}>\frac{8n}{\alpha}(\ln(ne)+4)$, we have for any $i\geq 0$,
$t_{1}>\frac{8n}{\alpha}\left(\ln\frac{ne}{2^{i}}+\frac{2\cdot(i+2)}{2^{i}}\right)\
.$ Hence our probability of failure can be upper bounded by:

$\mathbb{P}\left[\,\mathsf{fail}\,\right]\leq\sum_{i=0}^{\log
k}e^{-i-2}\leq\frac{1}{e^{2}}\frac{1}{1-1/e}\leq\frac{1}{4}\ .$

Claim 3: With probability at least $3/4$, for any set $K$, with $|K|\leq k$,
for $k>n/\alpha$, some query $Q\in\mathcal{Q}_{2}$ satisfies $|Q\cap K|=1$.

Similarly as in claim $2$ take any query $Q\in\mathcal{Q}_{2}$ and set $K$.
Let $k^{*}=|K|$. We know that $k^{*}\leq k$. We have:

$\mathbb{P}\left[\,|Q\cap
K|=1\,\right]=k^{*}\cdot\frac{1}{6k}\cdot\left(1-\frac{1}{6k}\right)^{k^{*}-1}\geq\frac{k^{*}}{6k}\cdot\left(1-\frac{k^{*}}{6k}\right)\geq\frac{k^{*}}{8k}\
.$

Hence, if $k^{*}\in[2^{i},2^{i+1}]$, then $\mathbb{P}\left[\,|Q\cap
K|=1\,\right]\geq\frac{2^{i}}{8k}$. We denote event $\mathsf{fail}$ as the
event that $\mathcal{Q}_{2}$ fails to hit any set with a most $k$ elements for
$k>n/\alpha$:

$\mathbb{P}\left[\,\mathsf{fail}\,\right]\leq\sum_{i=0}^{\log
k}2^{i+1}{n\choose
2^{i+1}}\left(1-\frac{2^{i}}{8k}\right)^{t_{2}}\leq\sum_{i=0}^{\log
k}e^{i+1}\cdot e^{2^{i}\ln\frac{ne}{2^{i}}}e^{-t_{2}\cdot\frac{2^{i}}{8k}}\ .$

Knowing that $t_{2}>8k(\ln(ne)+4)$, we have for any $i\geq 0$:
$t_{2}>8k\left(\ln\frac{ne}{2^{i}}+\frac{2\cdot(i+2)}{2^{i}}\right)$. Hence
our probability of failure can be upper bounded by:

$\mathbb{P}\left[\,\mathsf{fail}\,\right]\leq\sum_{i=0}^{\log
k}e^{-i-2}\leq\frac{1}{e^{2}}\frac{1}{1-1/e}\leq\frac{1}{4}\ .$

The probability that any claim fails is at most $1/3+1/4+1/4<1$. By the
probabilistic method we have that a sequence satisfying all three claims
exist. Now if we want to distinguish $K_{1}$ from $K_{2}$ we take
$K=K_{1}\;\triangle\;K_{2}$ and observe that by Claim 2 and 3, some query $Q$
has intersection of size exactly $1$ with $K_{1}\;\triangle\;K_{2}$. By Claim
1, each query has at most $\alpha$ elements hence feedback from query $Q$
under ${\mathcal{F}}_{\alpha}$ will be different for $K_{1}$ and $K_{2}$.
Hence, $\mathcal{Q}$ provides different feedbacks for any two sets of at most
$k$ elements.

If $t<n$, then surely $\alpha\geq 2\log_{2}n$ and we use the sequence of
queries $\mathcal{Q}$. Otherwise we simply pick a Round-Robin selector of size
$n$, where each query contains one unique element. Hence the final query
complexity is $\min\\{t,n\\}$. ∎

##  9 Discussion of results and open directions

Considering only polynomially-constructible query systems leaves some
interesting open directions. One such open direction is whether optimal-length
query sequence can be constructed in polynomial time or perhaps it is possible
to show some reduction that constructing a close-to-minimum query sequence is
hard (even if we know that it exists). Shrinking polylogarithmic gaps between
lower and upper bounds (existential) is another challenging direction, as well
as considering other interesting classes of feedback with an $\alpha$-capped
feedback, e.g., parity. We also believe that with some adjustment, Group
Testing codes could be applied to efficiently solve many open problems in
online streaming and graph learning fields.

## References

  * [1] W. H. Bay, E. Price, and J. Scarlett.  Optimal non-adaptive probabilistic group testing in general sparsity regimes.  arXiv preprint arXiv:2006.01325, 2020.
  * [2] N. H. Bshouty.  Optimal algorithms for the coin weighing problem with a spring scale.  In COLT 2009 - The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009.
  * [3] C.-C. Cao, C. Li, and X. Sun.  Quantitative group testing-based overlapping pool sequencing to identify rare variant carriers.  BMC bioinformatics, 15(1):1–14, 2014.
  * [4] J. Capetanakis.  Generalized tdma: The multi-accessing tree protocol.  IEEE Transactions on Communications, 27(10):1476–1484, 1979.
  * [5] J. Capetanakis.  Tree algorithms for packet broadcast channels.  IEEE transactions on information theory, 25(5):505–515, 1979.
  * [6] K. Censor-Hillel, B. Haeupler, N. A. Lynch, and M. Médard.  Bounded-contention coding for the additive network model.  Distributed Comput., 28(5):297–308, 2015.
  * [7] M. Cheraghchi and J. Ribeiro.  Simple codes and sparse recovery with fast decoding.  In 2019 IEEE International Symposium on Information Theory (ISIT), pages 156–160. IEEE, 2019.
  * [8] B. S. Chlebus and D. R. Kowalski.  Almost optimal explicit selectors.  In M. Liskiewicz and R. Reischuk, editors, Fundamentals of Computation Theory, 15th International Symposium, FCT 2005, Lübeck, Germany, August 17-20, 2005, Proceedings, volume 3623 of Lecture Notes in Computer Science, pages 270–280. Springer, 2005.
  * [9] S.-S. Choi and J. H. Kim.  Optimal query complexity bounds for finding graphs.  Artificial Intelligence, 174(9-10):551–569, 2010.
  * [10] A. E. F. Clementi, A. Monti, and R. Silvestri.  Selective families, superimposed codes, and broadcasting on unknown radio networks.  In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA, pages 709–718. ACM/SIAM, 2001.
  * [11] R. Clifford, K. Efremenko, E. Porat, and A. Rothschild.  Pattern matching with don’t cares and few errors.  Journal of Computer and System Sciences, 76(2):115–124, 2010.
  * [12] A. Coja-Oghlan, O. Gebhard, M. Hahn-Klimroth, and P. Loick.  Optimal group testing.  In J. D. Abernethy and S. Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 1374–1388. PMLR, 2020.
  * [13] G. Cormode, M. Garofalakis, S. Muthukrishnan, and R. Rastogi.  Holistic aggregates in a networked world: Distributed tracking of approximate quantiles.  In Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pages 25–36, 2005.
  * [14] G. Cormode and M. Hadjieleftheriou.  Finding frequent items in data streams.  Proceedings of the VLDB Endowment, 1(2):1530–1541, 2008.
  * [15] G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava.  Finding hierarchical heavy hitters in data streams.  In Proceedings 2003 VLDB Conference, pages 464–475. Elsevier, 2003\.
  * [16] G. Cormode and S. Muthukrishnan.  What’s hot and what’s not: tracking most frequent items dynamically.  ACM Transactions on Database Systems (TODS), 30(1):249–278, 2005\.
  * [17] G. Cormode and S. Muthukrishnan.  Combinatorial algorithms for compressed sensing.  In International colloquium on structural information and communication complexity, pages 280–294. Springer, 2006.
  * [18] P. Damaschke.  Threshold group testing.  Electronic Notes in Discrete Mathematics, 21:265 – 271, 2005.  General Theory of Information Transfer and Combinatorics.
  * [19] A. De Bonis, L. Gasieniec, and U. Vaccaro.  Generalized framework for selectors with applications in optimal group testing.  In Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings, volume 2719 of Lecture Notes in Computer Science, pages 81–96. Springer, 2003.
  * [20] G. De Marco, T. Jurdzinski, and D. R. Kowalski.  Optimal channel utilization with limited feedback.  In L. A. Gasieniec, J. Jansson, and C. Levcopoulos, editors, Fundamentals of Computation Theory - 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14, 2019, Proceedings, volume 11651 of Lecture Notes in Computer Science, pages 140–152. Springer, 2019.
  * [21] G. De Marco and D. R. Kowalski.  Searching for a subset of counterfeit coins: Randomization vs determinism and adaptiveness vs non-adaptiveness.  Random Structures & Algorithms, 42(1):97–109, 2013.
  * [22] A. Djackov.  On a search model of false coins.  In Topics in Information Theory (Colloquia Mathematica Societatis Janos Bolyai 16). Budapest, Hungary: Hungarian Acad. Sci, pages 163–170, 1975.
  * [23] B. Doerr.  Probabilistic tools for the analysis of randomized optimization heuristics.  CoRR, abs/1801.06733, 2018.
  * [24] R. Dorfman.  The detection of defective members of large populations.  The Annals of Mathematical Statistics, 14(4):436–440, 1943.
  * [25] D. Du, F. K. Hwang, and F. Hwang.  Combinatorial group testing and its applications, volume 12.  World Scientific, 2000.
  * [26] U. Feige and A. Lellouche.  Quantitative group testing and the rank of random matrices.  CoRR, abs/2006.09074, 2020.
  * [27] L. Galanis, Y. Wang, S. R. Jeffery, and D. J. DeWitt.  Locating data sources in large distributed systems.  In J. C. Freytag, P. C. Lockemann, S. Abiteboul, M. J. Carey, P. G. Selinger, and A. Heuer, editors, Proceedings of 29th International Conference on Very Large Data Bases, VLDB 2003, Berlin, Germany, September 9-12, 2003, pages 874–885. Morgan Kaufmann, 2003.
  * [28] R. Gallager.  A perspective on multiaccess channels.  IEEE Transactions on information Theory, 31(2):124–142, 1985.
  * [29] O. Gebhard, M. Hahn-Klimroth, D. Kaaser, and P. Loick.  Quantitative group testing in the sublinear regime.  CoRR, abs/1905.01458, 2019.
  * [30] P. B. Gibbons, Y. Matias, and V. Poosala.  Fast incremental maintenance of approximate histograms.  ACM Transactions on Database Systems (TODS), 27(3):261–298, 2002\.
  * [31] A. C. Gilbert, S. Guha, P. Indyk, Y. Kotidis, S. Muthukrishnan, and M. J. Strauss.  Fast, small-space algorithms for approximate histogram maintenance.  In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 389–398, 2002.
  * [32] A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. J. Strauss.  How to summarize the universe: Dynamic maintenance of quantiles.  In VLDB’02: Proceedings of the 28th International Conference on Very Large Databases, pages 454–465. Elsevier, 2002.
  * [33] V. Grebinski and G. Kucherov.  Optimal reconstruction of graphs under the additive model.  Algorithmica, 28(1):104–124, 2000.
  * [34] A. G. Greenberg, P. Flajolet, and R. E. Ladner.  Estimating the multiplicities of conflicts to speed their resolution in multiple access channels.  Journal of the ACM (JACM), 34(2):289–325, 1987.
  * [35] A. G. Greenberg and S. Winograd.  A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels.  Journal of the ACM (JACM), 32(3):589–596, 1985.
  * [36] M. Greenwald and S. Khanna.  Space-efficient online computation of quantile summaries.  ACM SIGMOD Record, 30(2):58–66, 2001.
  * [37] I. F. Ilyas, W. G. Aref, and A. K. Elmagarmid.  Supporting top-k join queries in relational databases.  VLDB J., 13(3):207–221, 2004.
  * [38] P. Indyk.  Deterministic superimposed coding with applications to pattern matching.  In 38th Annual Symposium on Foundations of Computer Science, FOCS ’97, Miami Beach, Florida, USA, October 19-22, 1997, pages 127–136. IEEE Computer Society, 1997.
  * [39] P. Indyk.  Explicit constructions of selectors and related combinatorial structures, with applications.  In D. Eppstein, editor, Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA, pages 697–704. ACM/SIAM, 2002.
  * [40] P. Indyk, H. Q. Ngo, and A. Rudra.  Efficiently decodable non-adaptive group testing.  In M. Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1126–1142. SIAM, 2010.
  * [41] W. Kautz and R. Singleton.  Nonrandom binary superimposed codes.  IEEE Transactions on Information Theory, 10(4):363–377, 1964.
  * [42] J. Komlós and A. G. Greenberg.  An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels.  IEEE Trans. Inf. Theory, 31(2):302–306, 1985.
  * [43] K. Lee, K. Chandrasekher, R. Pedarsani, and K. Ramchandran.  Saffron: A fast, efficient, and robust framework for group testing based on sparse-graph codes.  IEEE Transactions on Signal Processing, 67(17):4649–4664, 2019\.
  * [44] J. L. Massey.  Collision-resolution algorithms and random-access communications.  In Multi-user communication systems, pages 73–137. Springer, 1981\.
  * [45] E. Porat and A. Rothschild.  Explicit nonadaptive combinatorial group testing schemes.  IEEE Trans. Inf. Theory, 57(12):7982–7989, 2011.
  * [46] A. Ta-Shma, C. Umans, and D. Zuckerman.  Loss-less condensers, unbalanced expanders, and extractors.  In J. S. Vitter, P. G. Spirakis, and M. Yannakakis, editors, Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 143–152. ACM, 2001.
  * [47] J. X. Yu, Z. Chong, H. Lu, and A. Zhou.  False positive or false negative: Mining frequent itemsets from high speed transactional data streams.  In VLDB, volume 4, pages 204–215, 2004.