Scalable and Efficient Non-adaptive Deterministic Group Testing
Authors: Dariusz Kowalski
Dominik Pajak
Venue: NeurIPS 2022 Accept (2022)
Keywords: Quantitative Group Testing
Queries
Learning Theory
Non-adaptive
Deterministic Algorithms

Abstract: Group Testing (GT) is about learning a (hidden) subset $K$, of size $k$, of some large domain $N$, of size $n \gg k$, using a sequence of queries. A result of a query provides some information about the intersection of the query with the unknown set $K$. The goal is to design efficient (polynomial time) and scalable (polylogarithmic number of queries per element in $K$) algorithms for constructing queries that allow to decode every hidden set $K$ based on the results of the queries. A vast majority of the 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 of learning the set $K$. Others assumed unlimited computational power (existential results) or adaptiveness of queries (next query could be constructed taking into account the results of the previous queries) – the former approach is less practical due to non-efficiency, and the latter has several drawbacks including non-parallelization. To avoid all the abovementioned drawbacks, for Quantitative Group Testing (QGT) where query result is the size of its intersection with the hidden set, we present the first efficient and scalable non-adaptive deterministic algorithms for constructing queries and decoding a hidden set K from the results of the queries – these solutions do not use any randomization, adaptiveness or unlimited computational power.


Scalable and Efficient Non-adaptive Deterministic Group Testing
Dariusz Kowalski
Dominík Pajak
School of Computer and Cyber Sciences Augusta University, USA dkowalsk Caugusta. edu
Department of Pure Mathematics
Wroclaw University Science and Technology,
Infermedica, Poland dominik, Cominik.pajak@pue aaakpakk.eeeeeee edu.pl
Abstract
Group Testing (GT) is about learning a (hidden) subset K, of size of some large domain N, of size n > k. using a sequence of queries. A result of a query provides some information about the intersection of the query with the unknown set K. The goal is to design efficient (polynomial time) and scalable (polylogarithmic number of queries per element K) algorithms for constructing queries that allow to decode every hidden set K based on the results of the queries. A vast majority of the 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 of learning the set K. Others assumed unlimited computational power (existential results) or adaptiveness of queries (next query could be constructed taking into account the results of the previous queries) the former approach is less practical due non-efficiency, and the latter has several drawbacks including non-parallelization. To avoid all the abovementioned drawbacks, for Quantitative Group Testing (QGT) where query result is the size its intersection with the hidden set, we present the first efficient and scalable non-adaptive deterministic algorithms for constructing queries and decoding a hidden set K from the results of the queries these solutions do not use any randomization, adaptiveness unlimited computational power.
Introduction
In the Group Testing (GT) field, the goal is identify all elements of unknown K by asking queries. Originally GT was applied to identifying infected individuals in large populations using
pooled tests (26) which regained interest during COVID-19 pandemic 2 52 [56]- Recently GT found
applications in various areas of Machine Learning including approximating the nearest neighbor (2 simplifying multi-label classifiers [58) and accelerating forward pass of a deep neural network (1
All we initially know about set K that |K| S k. for some known parameter < n, and that is subset of some much larger set N with |N n. The answer to query Q depends on the intersection between K and Q and equals to Result K Q), where Result is some result function (also called feedback function in this paper).
The sequence of queries is correct solution to Group Testing and only if for any two different sets K1, K2 (satisfying some cardinality restriction), the sequence of answers for Ki and K₂ is different. Note that although this allows to uniquely identify the hidden set K based on the results of the queries, in some cases decoding of set K could be hard computational problem. The objective is: for given deterministic feedback function Result(-), to find a fixed sequence of queries that will identify any set K, and the length of this sequence, called the query complexity, is short as possible. In particular, we are interested in solutions that have query complexity logarithmic in n and polynomial in k.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Constructive algorithms
Lower bound
O n)
Ω h22
log n log k
k
O log
54
Ω
h:
lox n Tog k
(folklore)
Ō(k) Thm
(for a = k)
min
+ k)
(Thm
1
?
min
k
log log
(Thm
Table 1:
Asymptotic bounds on query complexity of solutions to non-adaptive deterministic QGT with Fo feedback. By constructive upper bound we mean query construction and decoding of hidden set in time poly(n). Symbol * stands for any valid value of the parameter a E {l,..., kij,, notations Ô and Q disregard polylogarithmic factors.
The most popular classical variant, present in the literature, considers function Result(-) that answers whether the intersection between K and Q is empty or not, c.f., 27 : 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 4 [24] and Quantitative Group Testing (QGT) B2 29).
In this paper we study the problem of Group Testing under more general capped quantitative result, where the result (feedback) is the size of the intersection up to some parameter E (1....,k]] and a for larger intersections. It subsumes and generalizes the two previously described classical result functions: the smallest case of a = =1 corresponds to the classical cmpty/non-empe feedback (beeping). while the case a = I captures the (full) quantitative feedback (classical QGT). Motivation for our research is twofold: first, to better understand the intermediate settings between the two classical GT models; second, to find efficient solutions for the capped settings that could be applied to other problems (see the Appendix).
Our focus is on non-adaptive deterministic solutions, in which queries are fixed (i.e., the same sequence applies to all hidden sets) and allow to discover (decode) any hidden set based on a- capped results. The primary goal is minimize the number of queries, called query complexity, and the second objective is to compute the queries and decode the hidden set in polynomial time. All existing polynomial construction/decodingg algorithms for beeping or quantitative feedbacks use O O(min (n, A log n1)) queries, c.f., [54]. General constructions developed in this work employ the concept of dispersion, c.f., [57] and combine it appropriately with other techniques. When instantiated for specific feedback parameter a E {1..... k}. (e.g., a = vk), they shrink the gap between the upper and lower bounds on the number of efficiently constructed queries nearly exponentially: from linear to polylogarithmic gap per hidden element. Together with our lower bound, they explain why sometimes a much smaller feedback is sufficient for decoding sets with similar efficiency. We show that parameter a has also different interpretations - it inversely relates to the number of occurrences of an element in the queries and to fault-tolerance (c.f., Section
1.1 Our Results (see also Table
We generalize the classical beeping and QGT models of Group Testing by considering a-capped re- sults, also called an a-capped feedback function, for an a E {I,...,k): for a hidden set K and query Q it returns Fa (Q n K) min [ n K|,a}, We study the query complexity of non-adaptive deter- ministic QGT in this general model. We focus on scalable (polylogarithmic number of queries per element) and efficient (polynomial time) constructing//ecodinng algorithms, and we show that it could be achieved if and only if the information cap a = (((Kk). particular, holds for classical QGT.
Main result- Polynomial--inn construction/deecdiing algorithms using almost optimal number of queries (Algorithms] and in Section g. Here almost-optimality means that the length of the constructed query sequence only polylogarithmicaly longer than the shortest possible sequence. The previous best polynomial-time solution used @ ( h:2 logn)) queries for all a 2 1 [54]] and we shrink it by factor O }r} polylog n). To achieve this goal, we define and build new types of selectors, called (Strong) Selectors under Interference (SSul and Sul, for short) based on the concept of (superimposed) dispersion. Although dispersion has been used before in GT, c.f., 100 44 as well as the classical superimposed codes, our technical novelty is twofold: first, we identified additional properties of selectors (c.g., avoiding interfering set with capped intersections), that could

---

not be formally deducted from the definitions of previous types of selectors, but allow to improve the solutions to QGT; second, we applied careful mathematical analysis to choose specific parameters of dispersers and superimposed codes and to prove that the new selectors' properties hold.
We also generalize the concept of Round-Robin query systems, where each query is singleton, to a--Rond-Robiin query systems, containing sets of size at most a. Such sequences are shorter than the simple
i.e., have length ((n/aa) polylog n), and, unlike a simple Round-Robin singletons' structure, are challenging to construct in a way to allow correct decoding based on a-capped feedback.
Theorem 1. There is an explicit polynomial-ting algorithm constructing non-adaptive queries n
QI,--. Qm for m= (min { ( polylog + k polylog n)), that solve Group Testing un- der feedback Fa with polynomial- time decoding. Moreover, every element occurs O( & polylog n) queries, and the decoding time is Om + K²
a polylog k polylog n.).
One of the consequences is that having the result function capped at = Vk, we obtain similar number of queries as with the actual result (i.c., returning the size of the whole intersection, up to k), which together with next lower bound establishes interesting inherited property of GT. The value a k seems to be sweet spot balancing two different phenomena superimposed coding and dispersion. Enriching the beeping model (i.e., a increases starting from 1) allows to improve the superquadratic query complexity of classical superimposed coding (used for the beeping feedback), and the improvement is roughly quadratic in terms of ax due to the nature of superimposed codes. On the other hand, limiting the full quantitative model (i.e., a decreases starting from k) increases the number of queries, starting from slightly superlinear, roughly linearly in a, as the nature of dispersion is linear. Both these phenomena equalize query complexities at a vk. This is illustrated in our construction in the beginning. the progress in learning relies on dispersion based Sul's for small a, then with the growth of a the length of used Suls becomes similar to the length of the code-based SSul; it happens for vk. The SSul allows to discover all the remaining elements and finishes the learning process. The last fact explains why further increase of a is not needed.
Lower bound (Section 5 The almost-optimality of our algorithms from Theorem | is justified by proving an absolute lower bound on the length of sequences allowing decode a hidden set based on feedback Fa 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 Fa. not restricted to polynomially constructed queries with polynomial decoding algorithm. Even more, some components of the lower bound are general: they hold for any a-capped feedback function, which will be formally defined later in Section The lower bound has three components: (k/a)², 22 nt/a, and k log 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 I up to polylogarithmic factor.
Theorem 2. Any non-adaptive algorithm solving Group Testing needs:
2 {min (())²
n
+ l
log Tog
queries under under feedback Fa.
.a
2 {min (1A) .a
queries under any feedback capped at a.
Document structure. We discuss related work on various variants of GT Section Section k we formally define the QGT problem and the generalized a-capped-results model. In Section 4 we present our polynomial-time query construction and decoding algorithms. Section proves the lower bound. Discussion of extensions, applications and future directions is given in Section 6 Additional Appendix contains more details: Appendix disicusse other related work; Appendix B shows details of extensions and applications; Our new selector tools are constructed and analyzed in Appendix
2 Previous and Related Work (see also Tables 1 and 2
Group Testing with general feedback functions have been studied in 47], where two parameters of feedback functions (cap and expressiveness) are shown influence the necessary number of queries.
In the standard feedback model, considered in most of the Group Testing literature 277. the feedback tells whether the intersection between query Q and set K is empty or not (sometimes it is also
3

---

Upper bound
First work with asymptotic bound
Difference from this paper
Jog zi log & log Tog K lo log ls
existential (super-exponential construction time)
k
adaptive
Jogan
randomized (only with some probability)
Table 2: Other related work on adaptive, randomized existential solutions to QGT for k.
called a beeping model). It it is a special case Fi of our feedback function. In this feedback model, Group Testing is known be solvable using O(k2 log(n/k)) queries (21 and an explicit polynomial- time construction of length O(k2 log n) exists [54] Best known lower bound (for k < vn) is C2kk2 log n/ log k) [12] This model is also similar to Angluin's notion of concept learning with disjointness queries [. The main differences are that in our model the learner is non-adaptive and that in the disjointness queries the feedback might include an element from the intersection.
The setting considered in this paper is also a generalization of an existing problem of coin weighting. In this problem, we have a set of coins of two distinct weights Wh (true coin) and wi (counterfeit coin), out of which up to are counterfeit ones. We are allowed to weigh any subset of coins on spring scale, hence task is to identify all the counterfeit coins. Such a feedback is a special case Fx of our feedback function. The problem is solvable with O log (n/kk) log k.) 377 non-adaptive (i.e., fixed in advance) queries and matching& a standard information-theoreet well as its stronger version proved for randomized strategies [24]. [ considers the problem of explicit polynomial-time construction of O( log(n/k)/ log k) queries that allows for polynomial time identification of the counterfeit coins. However, the algorithm presented in + 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 [б] but the resulting query complexity would be O polylog n). Thus, the solution in our paper the first explicit polynomial time algorithm constructing non-adaptive queries
can deduce the number of counterfeit coins in each weighting. The
lower bound of Q2k log(m/k) log k)), as
allowing for fast decoding of set K, with O(k polylog n) fixed queries.
An important line of work non-adaptive randomized solutions Quantitative Group Testing, started by (55) and being continued until recently B2 14 29 B, resulted in a number of algorithms
nearing the lower bound of 2k [n(m//) from 25 However, these results always assume some
restriction on & (typically k n for some 0 < 0 < 1), and similarly above, they may result in significant deviation from the actual set n is large. They also require a large number of truly random bits (in practice, algorithms have access only small truly random seeds, while randomized solutions typically have large number of Q(n log n log k) random bits to construct the queries) and typically do not offer any provable guarantees in case when an adaptive adversary could create/change the hidden set or introduce errors online during the learning process.
The bounds obtained in this paper match (up to polylogarithmic factors) the best existing results for the extreme cases of a = and a = k: The paper also bounds how the query complexity depends on the value of a between these extremes. Interestingly show, that the shortest- posssele query complexity of l polylog n is already possible for v/ and increasing from Vk to k does not result in further decrease of the query complexity.
Other interesting feedback function is Threshold Group Testing model includes a set of thresholds and the feedback function returns whether or not the size of the smaller than each threshold. In 2 the authors show that it is possible to
20 2
where the feedback
intersection is larger define an interval of /k log & thresholds resulting in an algorithm with ( log(n/k)) /k)/ log k) queries. Note that both those feedbacks are "inefficient" in view of our setting of a-capped feedbacks, because their feedback functions are not capped at any a < k. but they achieve similar query complexity as capped F FVJ feedback.
Superimposed codes and dispersers were already used in Group Testing. However, they either led to a super-quadratic (in k) number of queries, c.f., 46 M. or decoded only fraction of elements of the hidden set, see identified elements, decoding of all the elements requires over k2 queries, as proved in 2 10] 45
Recall that in solutions where query complexity depends on the number of

---

presents the first Group Testing solution with poly(ík, logn) decoding time, but super aueer-quarattcc query complexity. It is worth noting that our generalized solution achieves almost-lineat number of queries (for certain values of ()) 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 (Sul, SSul), which we prove to be satisfied by some combinations of those tools, and lead to efficient solutions in both query complexity and construction/deecdingg time.
3 The Model and the Problem
We assume that the universe of all elements N. with [N] n, is enumerated with integers 1, .,,,...?7 Throughout the paper, we will associate an element with its identifier. Let K, with |K] S k; denote a hidden subset of N chosen arbitrarily by adversary. Let Q (Q1...., Qm) be non-adaptive algorithm, represented by a sequence of m queries fixed prior to an execution.
A general feedback function F is function from subsets of N into an arbitrary domain. A function is applied to KnQ. A meaningful feedback function can range from simple empty/non-empl feedback up to returning all elements of the intersection. Consider feedback function F... that returns the size of an intersection if is at most a and a for larger intersections, i.e., Fa(QnK) = min [Q K] a.. Parameter a in feedback Fa is called feedback cap. A general class of feedback functions (used in our lower bound) with feedback cap a includes all deterministic functions that take subsets of N as input and for sets with more than elements output some arbitrary fixed value.
We say that Q solves Quantitative Group Testing (QGT), if the feedback vector allows for unique identification of set K. The feedback vector is defined as (Fa (Q n K), Fa (), K)...., Fa (Q K)). Thus, in order to solve QGT, the feedback vectors for any two sets K₁ and K₂ have to be different. We say that Q solves QGT 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 say that Q is constructible in polynomial time if there exists polynomial-time algorithm, that given parameters n, k a outputs an appropriate sequence of queries.
We assume that both coupled algorithms, construction and decoding, know n. k. Fa. W.L.o.g, in order to avoid rounding in the presentation, we assume that n and other crucial parameters are powers
4
Polynomial-time Constructions and Decoding
4.1 Combinatorial Tools
In this section we introduce two new combinatorial tools (Selectors- under- www---unnnne---r-eeeeee Interference and Strong- selectors-undes Interference) Indrrreeeenett-teeeeeeeeeee for our QGT solutions, and recall Dispersers and Balanced IDs.
For given sets K1, K2 C N and an element e E K1, we say that 5 C N selects v from K₁ under a-interference from K₂ if S n K (u) and |SS n Kg < Intuitively, is unique representative of K1 in S and the number of representatives of K2 in S is smaller than a.
beneleetoo-undr--nneeeeee (n, e, e, K. -SS-uul for short, is a sequence of queries S (Si,..., Sz) satisfying: for every set Ki C N of at most E elements and set K2 C N of at most k elements, there are at most el elements E Ki that are not selected from Ki under a-interference from K₂ by any query Si E S, i.e, set {u E K1 : Visa S ConK K1 # {u] or |S K2l 2 a} has less than el elements.
Definition (Selector under Interference (Sul)). An (n, E, c,
Disperser. Consider bipartite graph G (V, W, E), where [V] n, which is (f" = cl, c)- disperser with entropy loss 6, i.c., it has left-degree d, |W| Êd/5, and satisfies the following dispersion condition: for each L C V such that [L] > E* the set Na(L) of neighbors of L in graph G is of size at least (1 e) W.] Note that it is enough for us to take as e in the dispersion property the same value as in the constructed (n, K. a-S- S SI An explicit construction (i.e.. in time polynomial in n) of dispersers was given by (57] for any n. 2 L, and some ò Ollog nt). where d = (polylog n)] In the following the notation d and 5 will always denote the parameters of the disperser. Note that any improved construction of dispersers will immediately reduce the complexities of our algorithms. In Appendix C.T we will describe two disperser- based polynomial- time constructions of Sul and prove:
If someone considers c 2 1/3, we could use construction for c = 1/3 to get solution with better guarantees. *Optmal dispersers have d = O(1) and d Ollog n), but their polynomial time construction is an open problem.
5

---

Theorem 3. There is an explicit polynomial-time time construction of an (n, e, n. a) Sul. for any E, any a S lo such that (36( K, for any constant E (0,1/3), of size O(min {n. Edd log n) Moreover, every element occurs in O(d log queries.
Theorem 4. There is explicit polynomial-tin construction of an (n,l,e,,, a, - for any E, any I k such that &. 35x//o for any constant (3,1/3). of size O (min {n, a ndd logn). Moreover, every element occurs in Odō logn) queries.
add log n
a
Definition 2 (Strong Selector under Interference (SSul)). An (n, f, K. (eto:)))tro-n-eeeee Strron--Seletto--uuder Interference, (n, E, K. o:S-Suu for short, is a sequence of queries 'T = (Ti,..., .Tg) satisfying: for every set K₁ S. N of most i elements and set K2 S N of most elements, every element v E K1 is selected from K1 under a-interferennce from K₂ by some query Ti E T, i.e. set {U K1 : Viga T.n K1 + {u} [TinKy 2 a} is empty.
An (n, E, K, a) -St--SSn--Seeecttte tatrong--Secccoo-udddd-neeeereee under-Inte eedereeetereere In Appendix C.2 we describe a polynomial-time construction of SSul, which essentially is a [4 construction for adjusted parameters, and prove that it satisfies the SSul property. Theorem 5. There is an explicit polynomial-time construction of an (n, l, K. a--SSul of length O(o2 n), provided E 2 30k/ox /. Moreover, every element occurs in O log, π) queries.
could be also viewed as (n, E, 0, K. a) --Selccco
N has a unique ID represented by 2 log, n bits, in which the number of I's is the same as the number of O's; e.g., take a binary representations of elements and n 1-1, i, each in logz bits, and concatenate them (recall n [N)). Balanced IDs have previously been used in algorithms for decoding elements in Group Testing (see e.g., [50
Balanced IDs. Each element
4.2 Construction of Queries, Decoding and Analysis (Proof of Theorem
Algorithm constructing queries. Assume a 2 2 and k > 35k/(a - 1) (the opposite case will be considered later) and let us take (n, e, 1/2, k, a 1)-Sul S(O, for being a power of 2 ranging down from & to <ōk:(a 1) (w.l.o.g we could also assume that 3ōk/(a 1) is a power of 2). Next, for each set 5 in these selectors we add the following family R(S) = (S)) logg." of sets Rs(S)= = {u E S [w/2 = mod 2}. Intuitively R2(S) the set of elements from that have 1 on i-th least significant bit of Balanced ID. Let us call the obtained enhanced selectors (i.e., with additional families RSS), for every set S in the original selector) S(4) Then we concatenate selectors R(S(1). starting from the largest & = k, to the smallest value l = 3ōk: a 1). An (n. 35k//(a 1), k, a 1)-SSul T concatenated at the end, with the same replacement of bits 1 and 0 that gives R(T) as in the above (n, f, 1/2, k. v 38k//aa - 1) then the sequence equals to (n, k; k, aSS-Sull T concatenated as in the above with R.).). Algorithm| presents pseudocode of the construction algorithm for a >> 1.
2
1)-Sul's. In the case, where = 1 or
Algorithm 1: Construction of sequence of queries solving QGT with a-capped feedback.
Input: Disperser G of degree and entropy loss L. <- k Q + ():
T <- (n, 36k/ - 1), k. 1)-SSul;
while L
36k do
11 foreach T do @append(T);
a-I
S (n, 1/2, k,
S)-Sul
4
foreach E do
for 1 to 2oog n do 13
Qapppen((S)
(T) <- {u E : Lu/2 =1 mod 2}:
for i 1--110 to 2 log, n do
/* Add set of elements from 5 that have on
Cappend (R,(T) (T)):
16 return Q
i-th least significant bit of Balanced ID. (2( < freS: |0/2-11 */
7
mod 2):
@appped(RR(S)); (S))));
8 - t/2:

---

(16) (10)
..... = = = =644, 16,12,,, 16)-Su1
52)
82)
S(32)
(64,32, 1/2, 32, 16)-Sul
(Ti, T2... 3 T (64, 16)-SSul
R
100 R ((6)))
.52 R (
Tú. (T.)
for decoding 16 foul of 32) hidden elements
for decoding 8 (out of maining 16) hidden elements
for decoding the remaining 8 hidden elements
Figure 1: An example of sequence of queries produced by Algorithm 1 for n - 64, = =22 a 17.
For simplicity we assume that 16 > a-1 2 8.
36k
Decoding algorithm. During the decoding algorithm we process, in subsequent iterations, the feedbacks from enhanced selectors S14) for L = k, , 38k/ ( 1). We will later prove, by induction, that during processing S(4), , new elements from K are decoded. To show this, we consider any iteration and let set K₁ be the set of the elements that have been decoded in previous iterations while set K2- K' \, K2 be the set of unknown elements. We treat K₁ as the interfering set and, by the properties of (()), we know that for at least 2/2 elements v, there exists a query S E s(0), such that v E S, [ S| < a 1, K2 S = 1. We observe that since we already know the identifiers of all the elements from the interfering set K1, then using feedbacks from the additional queries R(S) (corresponding to balanced IDs) we can exactly decode the identifier of e. We do this for all 2/2 clements that are possible to decode in this iteration and we proceed to the next iteration. After considering all delectors-unders cetrssuunner--neffeeeneec we have only at most 3ōk/(a 1) unknown elements. complete the decoding we use a Sewnng-Selectorunnncee Inter--nterfferece,, where the decoding procedure is exactly the same as in the case of Sul (the interfering set is also the set of already decoded elements). The properties of SSul guarantee that we decode the identifiers of all the remaining elements from K. See the pseudocode of decoding Algorithm 2 for details of deocding for a 1. the case where a = the decoding is straightforward, as the SSul guarantees in this case no interference, hence the results (due to our enhancement 7) contain exactly the identifiers of the elements from set K.
Lemma 1. There is an explicit polynomial- time algorithm constructing non-adaptive queries Q1..... Qm and decoding any hidden set K of size at most k from the feedback vector in polynomial time, under feedback Fa and for = O((*) ((())22) 12252log" log" n + kdō log" n) queries. Moreover, every element occurs in
n + d8 log n) queries.
Proof. We start from describing a procedure of revealing elements in any given set K of at most elements, together with formal (inductive) argument of its correctness. Our first goal is to show that by the beginning of S(O), for stepping down from k to 35k/(a 1), we have not learned about the identity of at most 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 & = elements. We prove the inductive step: by the end of S(t), at most f/2 elements are not learned. We set K₂ to be the set of learned elements and K; = K K2. Clearly, [K2] < k. and by the inductive assumption K S E k. For such K1 and K2, by the definition of Sul, there are at most f/2 elements from K1 that are not occurring in some round without other such elements with at least a 1 of already learned elements from K2. Consider previously not learned element v E Ki, for which there exists a good query in S(0), i.e., query S E S(0) such that S n K, {v) and |S K2 a 1. At this point of decoding of set K we know the Balanced IDs of all elements from set K2. Hence we can calculate the 2 logg n-bit feedback vector n. from sets K₂ R, (S), K2 (S))...... K₂ n Ro (S). We compare this feedback vector with the output of the enhanced selector, which is the feedback vector for sets K n Ri (S), K n Kn R log, 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 I's is different from loga n, or in case F. n S) = a (recall that S is also in the constructed selector) the feedback from this R(S) is ignored. This is done to avoid misinterpreting the feedback and false discovery of an element which not in K. Indeed, first note that the fact K n 2 a will automatically discard the part of the feedback from Kn n Rí (S), K O (S), K n R2 (S), as indicates that the intersection is too large to provide correct decoding of an element. Second, assuming KK n S| a, if there are no elements
7

---

Algorithm 2: Decoding of the elements for QGT with a-capped feedback.
Input: Result(Q) for queries Q E Q constructed by Algorithm based on Sul ( for & being powers of 2 stepping down from k to 381 and SSul T. /* Set Kace accumulates the decoded elements. */
a-1
l < k, Kace <- 0; 36k
while > a-1 do
/* We decode 1/2 elements in each iteration.*/
for i f 1 to 1/2 do
/* Look for query for which we can decode a new element. foreach E s(() do if Re) a and |S Kacel = Result(S) 1 then Kace + Kace U [ Kace);
l e-1/2 while L >00 do
/* Iteratively decode all the remaining elements. +/
foreach T' E T do if Result(T) Kacc f Kace U Elementt)) )
10
and Kace Result(T) then Kace)))
11
1-1;
13 return Kace
Procedure Decode Kace)
1 2- 0:
for j loga n downto do
/* Take the feedback from set R2(Q). Calculate the feedback from set (Q), if hidden set was exactly K The difference is j-th least significant bit of Balanced ID of new element v.
2 Result(R,(Q)) (Ry(Q) Kacel
return
in K₁ n S then the difference between feedbacks gives vector of zeros, and there will be least two elements in K1 n S, the difference between feedbacks will contain a value of at least 2 or all I's, it will be a bitwise sum of least Balanced IDs of log, n ones each. By the definition of Sul can find 1/2 such elements This shows that during decoding of enhanced S(O) we learn the identities of 8/2 new elements. This completes the inductive proof. Note here that the inductive step, being one of Ologg n) steps, defines 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, 35k/(a - 1), k. a 1)-SSul we have not discovered at most 35k/(a 1) elements. Thus, by definition, (n, 35k//a 1), k. SS- combined with Balanced IDs reveals all the remaining elements in the same way as the Sul's above the only difference in the argument that instead of leaving most f/2 undiscovered elements in the l-th inductive step, due to the nature of Sul's, the SSul guarantees that every undiscovered element will occur the decoding algorithm defined this way works in polynomial time. By Theorem 3 the length of (n, f, 1/2, k a--Sul is Omin n, fdo log n²)), which sums up to O(kdō log" n), and is multiplied by (log nz) due to amplification by Balanced IDs. By Theorem the length (n, 35k/ a, k. a)-- SSul is )((=)² log" n), and it is also increased by factor O n) due to Balanced IDs. we apply the above reasoning with respect to the number of queries containing an element, get that every element occurs in O log" n + do log" n) queries.
good query. The same argument as for Sul's proves that
Implementing a- c-Round-Robin for large values of k/a. The question arises from the previous result one could efficiently construct a shorter sequence of queries if (k/a)² > n/a? In the case of full feedback (i.e., a 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 arbitrary value of < k, however the lower bound in Theorem suggest that in such case there could exist a shorter query system of length O((k + (n/a)) polylog n). Indeed, modify our construction in such case, we could obtain such goal. Namely, we concatenate:

---

selectors S(A) for being decreasing powers of 2 from & = k to E = 68k/ (a 1): selectors ( for being decreasing powers 2 from & = 3 (a - 1) to =
In the case, where k > (0k:/(a- 1). enhance them based on Balanced IDs, as in the previous construction. Then, applying Theorem for concatenated ( and Theorem for concatenated S ((9), instead of combination of Theorems and it was in the proof of Lemma I
then the construction contains only selectors 51 Then
with respect to S(O,, we get the following result.
Lemma 2. There is explicit polynomial-ting algorithm constructing non-adaptive queries Qi..... Qm and decoding any hidden set of size at most k I n. from the feedback vector in polynomial time, under feedback Fa and for m O(k n/oidd log n) queries. Moreover, each element occurs in (dd log" n) queries.
Proof. The proof is analogous to the proof of Lemma except that we continue proving the invariant until 6ōk/(a (a- 1), using same properties guaranteed by Theorems and continue the invariant until & = 1, using Sul's of slightly different length formula from Theorem 4 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 Then, by Theorem 3 for concatenated { and by Theorem for concatenated 8((", argue that the total length of the obtained sequence is m ( n (2)ddlog" n). Indeed, the first part results from the telescoping sum for different & and the second component is a logarithmic amplification of the original (( /a) log n) length of Sul's; all amplified by Ollog n) due enhancement of the used Sul's by Balanced IDs. In all the components, every element belongs to Odō log n.) queries, by Theorems and in the final sequence it occurs in ( log" n) queries.
Combining Lemma M with Lemma - gives Theorem Note that in both lemmas the decoding algorithm proceeds
each time spending polylogarithmic time 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 element in the queries (polylogarithmic).
Lower Bound
2 We will first show the min(n/cn aa, k2 /a²] component. Assume that sequence of queries Q1, Q2. Q2 of length ł solves Group Testing. We want to show the lower bound that hence we assume that the feedback function F returns the whole set (i.e., the identifiers of all the elements). Recall that F works only for sets with at most elements. We begin by proving the following:
Proof of Theorem
holds for any feedback function capped
Claim A: For any set K, with | < k and any E K, there must exist E (1,2,.... such that x Q and JK n+1+= S
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* {x*}. }. For any query that does not contain x², the feedback is clearly identical. For any query Qr, such that x² Qr, we have [Q,k 2 a and Q+ [x*)))] a and sets K* and K* \ {2*) are indistinguishable under any feedback capped at a hence the sequence of queries does not solve the problem. This completes the proof of Claim
Take all queries that have at most a + 1 elements and all elements that belong to such queries. We have: N. Ure 1SQ. Q- and remaining elements N; N \ N,. Consider two cases: Case 1: [Nal 2 n/2.
Observe that: 2 [T (1,2, ..., , 101 10/ a ++++)>
N₂ a+1 2(++1)
Case 2: [ 2 n/2.
In this case, we take an arbitrary subset K1 of k/2 elements from Nj. For every element æ E K1, we consider set queries Q(x) (Q, E (Q1, Q2..... Qt) I E Qr, 1k, S a+1). We show:
Claim B: For every E Ki, we have [Q(x)) > & that for some x² E Ki we have [Q(x") <
F[ The proof is by contradiction. Assume 2(+22). Then, for every query Q E Q(x"), we take
A

---

a 2-22-QQ4 K1 elements from Q K1 Such elements exist since |Q] 2 a + 2. Choose such elements for each query in Qx**) and gather them in set Kg. Note that since [[2(2)) )| < 2[++2]
then K2| k/2. Now observe that set K1 U K2 and element xt violate Claim A. The obtained contradiction completes the proof of Claim B.
Now observe that each query belongs to at most 1 sets ((x) for different values of K1. Thus: t Lack, [Q(x))
+(a+)) To complete the proof observe that any algorithm must fall either into Case 1 or Case 2. hence any algorithm needs to use ? (min(n/o, o. x²/a²)) queries.
g²
a++
log queries, observe that the feedback To see that any algorithm in Fa feedback model at least loog a vector must be unique for each set K with at most & elements. Hence we need at least (?) different
feedback vectors for different sets. Feedback has at most values hence we get o² (+) and
I E (2 E This completes the proof of Theorem
Togo
Extensions, Applications and Open Directions
Observations. The size of response to a capped quantitative query is not much bigger than beeping- log a bits one bit of heeping- whereas the number of queries is smaller by a factor of a² compared to beeping. Thus, even after normalization of the query complexity by the inverse of the size of the feedback, in the a-capped model it is nearly a² times better than the classic beeping, up to a = vk.
Although optimizing the construction time is not main focus, it is actually small. E.g., for Vk, the construction of all queries takes time (nn/k). Most of the complexity comes from the construction of SSul (Alg 4) - for each element of the universe, we consider ((vk) zeros some polynomial. We use logarithmic number of Suls in the construction, but each takes only ((n) time (Alg 3): in Sul for every element we list its neighborhood in disperser in polylogarithmic time (57 and take the Cartesian product with a polylogarithmic Reed-Solomon type of codeword.
Fault-tolerance. Algorithms and 2 are fault-tolerant with respect f I c k adversarially jammed results, for some sufficiently small constant c > 0- here by jammed result we understand receiving a null as result of query. It also tolerates stochastic failures, where result is jammed with probability p
Indeed, in adversarial failures observe that, by dispersion, & could be made negligible (by right selection of constant c) with respect to the number of selected elements in Sul, and it is also smaller than the number of single occurrences (i.c., without interference from other -- elements) of an element in SSul. Thus the analysis of the algorithms hold (the original analysis have margins to accommodate those additional negligible jamming, they asymptotic upper bounds). The tolerance of stochastic failures follows from the fact that a random p-fraction of results of queries coming from Sul's and SSul are again negligible from perspective of the fraction of correctly encoded elements and can be accommodated by our asymptotic analysis.
done with only
Theorem 6. Algorithms I and tolerate J S c- adversarial jammings and stochastic jammingss with probability S c, for some sufficiently small constant c >> 0.
Other applications. Applications to efficient GT and dynamic maintenance of multi-sets, graphs, as well as to Private Parallel Information Retrieval and coding, are detailed in Appendix
Open directions. Considering only polynomially-construeee ing open directions. One such 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 nearly-shortest query sequence is computationally hard (even if we know that it exists). Shrinking polylogarithmic gaps between lower and (existential) upper bounds and improving constants is another challenging direction, well as considering other interesting classes of GT models with a-capped results, e.g.. parity. We also believe that with some adjustment, capped GT codes could be applied to efficiently solve many open problems in online streaming, communication and graph learning fields.
query systems leaves some interest-
Acknowledgments and Disclosure of Funding
Dominik Pajak was supported by the National Science Centre, Poland (NCN), grant UMO- 2019/33/B/ST6/02988 Dariusz R. Kowalski was supported, part, by the National Science Center, Poland (NCN), grant UMO--2017/2////5566/0000
10

---

References
[1] D. Angluin. Queries and concept learning. Machine learning, 3(4):319-442, 1988.
[2] N. Augenblick, J. T. Kolstad, Z. Obermeyer, and A. Wang. Group testing in pandemic: The role frequent testing, correlated risk, and machine learning. Technical report, National Bureau of Economic Research, 2020.
[3] W. H. Bay, E. Price, and J. Scarlett. Optimal non non-adaptive probabilistic group testing in general sparsity regimes. arXiv preprint (rXiv:2006.0132. 2020.
[4] N. H. Bshouty. Optimal algorithms for the coin weighing problem with a spring scale. COLT 2009 The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009.
[5] 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.
[6] J. Capetanakis. Generalized tdma: The multi-accessing tree protocol. IEEE Transactions on Communications, 27(10):446611844 1979.
[7] J. Capetanakis. Tree algorithms for packet broadcast channels. IEEE transactions on information theory, 25(5)5005-515, 1979.
[8] K. Censor-Hille., B. Haeupler, N. A. Lynch, and M. Médard. Bounded-contentee coding for the additive network model. Distributed Computing, 2865):997330, 2015.
[9] M. Cheraghehi 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.
[10] B. Chlebus and R. Kowalski. Almost optimal explicit selectors. M. Liskiewicz and R. Reischuk, editors, Fundamentals of Computation Theory, 15th International Symposium, FCT 2005, Lübeek, Germany, August 17-20, 2005, Proceedings, volume 3623 of Lecture Notes in Computer Science, pages 270-280. Springer, 2005.
[11] S.-S. Choi and J. Kim. Optimal query complexity bounds for finding graphs. Artificial Intelligence, 17)5510))551-56)) 2010.
[12] A. E. 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.
[13] R. Clifford, Efremenko, E. Porat, and Rothschild. Pattern matching with don't 't cares and few errors. Journal of Computer and System Sciences, 76(2):115-124 2010.
[14] 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.
[15] G. Cormode, M. Garofalakis, S. Muthukrishnan, and R. Rastogi. Holistic aggregates in networked world: Distributed tracking of approximate quantiles. Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pages 25-36, 2005.
[16] G. Cormode and M. Hadjieleftheriou. Finding frequent items in data streams. Proceedings of the VLDB Endowment, 1(2):1530-1541, 2008
[17] G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava. Finding hicrarchical heavy hitters in data streams. In Proceedings 2003 VLDB Conference, pages 464-475. Elsevier, 2003.
[18] G. Cormode and S. Muthukrishnan. What's ss hot and what's not: tracking most frequent items dynamically, ACM Transactions Database Systems (TODS), 30(1):249-2788 2005.

---

[19] G. Cormode and S. Muthukrishnan. Combinatorial algorithms for compressed sensing. In International colloquium on structural information and communication complexity, pages 280-294. Springer, 2006.
[20] P. Damaschke. Threshold group testing. Electronic Notes in Discrete Mathematics, 21:265 271, 2005. General Theory of Information Transfer and Combinatorics.
[21] A. De Bonis, L. Gasieniec, and U. Vaccaro. Generalized framework for selectors with applica- tions 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 Computer Science, pages 81-96. Springer, 2003.
[22] G. De Marco, T. Jurdzinski, and D. R. Kowalski. Optimal channel utilization with limited feedback. J. Comput. Syst. Sci., 119:21-33, 2021.
[23] G. De Marco, T. Jurdzinski, D. R. Kowalski, M. Rózanski, and Stachowiak. Subquadratic non-adaptive threshold group testing. J. Compud. Syst. Sci., 111:42-56, 2020.
[24] G. De Marco and D. R. Kowalski. Searching for a subset of counterfeit coins: Randomization determinism and adaptiveness non-adaptiveness. Random Structures & Algorithms, 42(1):97-10%% 2013.
[25] A. Djackov. On search model of false coins. In Topics in Information Theory (Colloquia Mathematica Socieiatis Janos Bolyai 16). Budapest, Hungary: Hungarian Acad. Sci, pages 163-170, 1975.
[26] R. Dorfman. The detection of defective members of large populations. The Annals of Mathe- matical Statistics, 14(4):436 440, 1943.
[27] D. Du, K. Hwang. and F. Hwang. Combinatorial group testing and its applications, volume 12. World Scientific, 2000.
[28] J. Engels, B. Coleman, and A. Shrivastava. Practical near neighbor search via group testing. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 9950-9962, Curran Associates, Inc., 2021.
[29] U. Feige and A. Lellouche. Quantitative group testing and the rank of random matrices. CoRR, abs/2006.0900 09074, 2020.
[30] L. Galanis, Y. Wang, S. R. Jeffery, and D. 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.
[31] R. Gallager. A perspective on multiaccess channels. IEEE Transactions on information Theory, 3 31(2):124-142, 1985.
[32] O. Gebhard, M. Hahn-Klimroth, D. Kaaser, and P. Loick. Quantitative group testing in the sublinear regime. CoRR, abs/1905.01458, 2019.
[33] 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.
[34] A. C. Gilbert, S. Guha, P. Indyk, Y. Kotidis, S. Muthukrishnan, and M. Strauss. Fast, small- space algorithms for approximate histogram maintenance. In Proceedings of the thiry-fourth annual ACM symposium Theory of computing, pages 389-398, 2002.
[35] A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss. How to summarize the universe: Dynamic maintenance of quantiles. In VI 02: Proceedings of the 28th International Conference Very Large Databases, pages 454-465. Elsevier, 2002.
12

---

[36] S. Gollakota and D. Katabi. Zigzag decoding: combating hidden terminals in wireless networks. In V. Bahl, D. Wetherall, S. Savage, and I. Stoica, editors, Proceedings of the ACM SIGCOMM 2008 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Seattle, WA, USA, August 17-22, 2008, pages 159-170. ACM, 2008.
[37] V. Grebinski and G. Kucherov. Optimal reconstruction of graphs under the additive model. Algorithmica, 28(1):104-124, 2000.
[38] 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.
[39] 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.
[40] M. Greenwald and S. Khanna. Space-efficient online computation of quantile summaries. ACM SIGMOD Record, 50(2):58-66 2001.
[41] E. Hradovich, M. Klonowski, and D. R. Kowalski. Contention resolution on a restrained channel. In 26th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2020, Hong Kong, December 2-4, 2020, pages 89-98. IEFF, 2020.
[42] I. F. Ilas, W. G. Aref, and A. K. Elmagarmid. Supporting top-k join queries in relational databases. VLDB J., 13(3):207-211, 2004.
[43] 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.
[44] P. Indyk. Explicit constructions of selectors and related combinatorial structures, with applica- tions. In D. Eppstein, editor, Proceedings of the Thirteenth Annual ACM-SIAM Symposium Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA, pages 697-704. ACM/SIAM, 2002.
[45] 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.
[46] W. Kautz and R. Singleton. Nonrandom binary superimposed codes. IEEE Transactions Information Theory, 1044)33633377, 1964.
[47] M. Klonowski, D. R. Kowalski, and D. Pajak. Generalized framework for group testing: Queries, feedbacks and adversaries. Theor. Comput. Sci., 919:18-35. 3-,,, 2022.
[48] 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.
[49] D. R. Kowalski and D. Pajak. Light agents searching for hot information. In L. D. Raedt, editor, Proceedings of the Thirty-Fire First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 363-369. ijeai.org, 2022.
[50] K. Lee, K. Chandrasckher, R. Pedarsani, and K. Ramchandran. Saffron: A fast, efficient, and robust framework for group testing based on sparse- -raph codes. IEEE Transactions on Signal Processing, 67(17):66494466 2019.
[51] W. Liang and J. Zou. Neural group testing accelerate deep learning. In 2021 IEEE Interna- tional Symposium on Information Theory (ISIT), pages 958-963. IEEE, 2021.
[52] S. Mallapaty et al. The mathematical strategy that could transform coronavirus testing. Nature, 583(7817):504- 505, 2020.
[53] Massey. Collision-resolution algorithms and random-access communications, In Multi-user communication systems, pages 73-137. Springer, 1981.
13

---

[54] E. Porat and A. Rothschild. Explicit nonadaptive combinatorial group testing schemes. lEEE Trans. Inf. Theory, 57(12))7922-798, 2011.
[55] A. Sebö. On two random search problems. Journal of Statistical Planning and Inference, 11(1):23-31, 1985.
[56] N. Sinnott-Armstrong, D. L. Klein, and B. Hickey, Evaluation of group testing for sars-cov-2 ma. MedRxiv, 2020.
[57] A. Ta-Shma, C. Umans, and D. Zuckerman. Loss-less condensers. unbalanced expanders, and extractors. In J. S. Vitter, G. Spirakis, and M. Yannakakis, editors, Proceedings 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 143-152. ACM, 2001.
[58] S. Ubaru, S. Dash, A. Mazumdar, and O. Gunluk. Multilabel classification by hierarchical partitioning and data-dependent grouping. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 22542-22553. Curran Associates, Inc., 2020.
[59] 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.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] [Yes], [No], or [N/A] You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license the code and datasets? [Yes] See Section ??.
Did you include the license the code and datasets? [No] The code and the data proprietary.
Did you include the license to the code and datasets? [N/A]
Please do modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Our abstract and introduction states the theoretical results that are later proven our paper.
(b) Did you describe the limitations of your work? [Yes] Our assumed model (including the result function) is described in Section 3
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Our result is theoretical hence does not have any direct negative impact. Also none of the existing solutions to the Group Testing (which a field with almost 80 years of history) were harmful to the society.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The assump- tions are given in a statement of each theoretical result.
(b) Did you include complete proofs of theoretical results? [Yes] Some combinatorial
constructions (used in proofs of Theorems 5), are included Appendix C
3. If you experiments..
14

---

(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you's re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "yODbv66Y8u1", "reviewer": "Reviewer_KFv3", "summary": "In this work, the authors look at the problem of group testing where we are interested to learn about a hidden subset K of size k of a universe N of size n >> k. The authors assume access to subset queries that return its intersection size with K or $\\alpha$ if the latter exceeds $\\alpha$. The special cases $\\alpha=1$ and $k$ have been extensively studied before, while the general case has not been studied so far. The authors give a non-adaptive deterministic algorithm with an almost optimal query complexity.\n\ncaveat: I did not go through the proofs or technical lemmas in great detail.", "questions": "None.", "limitations": "None.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The problem is interesting and the presented results are significant.\n\n- previous works only looked at the special cases $\\alpha=1$ and $k$, whereas they consider the general problem\n- their upper and lower bound theorems are significant as they match up to small factors\n- interestingly they observe that the query complexity does not change by much as $\\alpha$ grows from $\\sqrt{k}$ through $k$ (LN# 134)\n- they give new results for certain combinatorial objects (SuI, SSI, dispersers)\n- their algorithms do not use any randomization, adaptiveness, or unlimited computational power, which is harder for upper bound\n\nWeakness: \n\n- the results are not supported by experiments (soundness).\n- a tighter query complexity characterization, even though not in polytime, is lacking (LN# 379) (contribution)\n- small examples to motivate/explain their algorithms or insights would have made the paper more readable (presentation)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "axc6Bdblm9n", "reviewer": "Reviewer_4QpY", "summary": "In group testing, the goal is to identify $k$ defective objects among a total population of $n$ objects, by designing pools of objects for some pre-determined test, and then recovering the identities of the defective objects from the outcomes of the test. The standard notion of group testing reveals whether or not a defective object is included in a pool for each test. This paper considers quantitative group testing, where each test reveals the number of defective objects included in the test, up to a cap $\\alpha$. The main result is a non-adaptive deterministic algorithm that uses roughly $\\tilde{O}(k^2/\\alpha^2)$ queries and decoding time. A nearly matching lower bound on the number of necessary queries is achieved for any non-adaptive algorithm.", "questions": "Are there specific applications for quantitative non-adaptive deterministic group testing algorithms? I think even the Private Parallel Information Retrieval (PPIR) application in Appendix B is a good motivation for quantitative group testing and in general non-adaptive group testing permits simultaneous queries instead of sequential queries, but I'm missing a situation where it would be good to have all of these demands simultaneously.", "limitations": "I do not see any potential negative societal impacts directly resulting from this work. ", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The nearly matching upper and lower bounds are nice. Achieving an efficient decoding time is also an important aspect of the results in this paper. The techniques seem clearly above the bar for NeurIPS, but the current presentation is difficult for me to understand the proposed algorithm. For instance, it seems a key technical contribution is a combinatorial object called the selector under interference (SuI). Its construction is briefly described in appendix C using $(n,3\\delta)$ strong selectors of Kautz and Singleton. However, neither the construction of the strong selector nor the relevant properties of the strong selectors are described. Thus the proof of correctness of the SuI is not accessible to me, e.g., statements such as line 700 invoke properties of the strong select that do not seemed to be discussed (please correct me if I am missing something!) Given that this is a purely theoretical paper, I think greater emphasis should be placed on the presentation, such as intuition for the individual components of the algorithm. For instance, the additional exposition in Section C.2 comparing the strong-selector-under-interference (SSuI) construction with a Reed-Solomon code was quite helpful. \n\nMore generally, I am concerned about the conceptual contribution of this paper within the context of NeurIPS. Although there is some precedence for group testing at NeurIPS, quantitative non-adaptive deterministic group testing seems significantly more limited. Indeed, I'm not sure that any of the motivations mentioned in this paper particularly require quantitative non-adaptive deterministic group testing, especially since randomized algorithms from previous work can achieve a smaller number of queries. Perhaps the authors can address this in their response.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RBFMFL-R6Cu", "reviewer": "Reviewer_NXCq", "summary": "This paper considers a group testing where the goal is to identify all elements of an unknown set K of size k from large domain N of size n by asking a non-adaptive (capped) quantitative query where query result is the size of its intersection with the hidden set capped by some parameter \\alpha. The main contribution of this paper is on proposing a polynomial-time construction algorithm constructing non-adaptive queries of length m=(\\min(k^2/alpha,n/alpha)+k)*polylog n that allows polynomial-time decoding. By proving a lower bound on the length of queries, it is also shown that having the cap size alpha=\\sqrt{k} is already optimal in achieving the shortest possible query complexity. ", "questions": "* What are the possible applications/motivations of capped quantitative query? How effective such type of query is compared to simple binary beeping group testing when the sample complexity is properly normalized by the query complexity? \n\n* Can the authors provide some intuitive explanation of why the cap size of \\alpha=\\sqrt{k} guarantees the optimality sample complexity (polylogrithmic number of queries per element) and why increasing \\alpha does not provide much information gain that can change the order of sample complexity? Does this claim hold when one consider the normalized sample complexity (normalized by the query complexity)? \n\n* Any suggestion to improve the poly(n) time complexity of query construction? \n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* Proposes a polynomial-time construction algorithm constructing non-adaptive queries of length m=(\\min(k^2/alpha,n/alpha)+k)*polylog n that allows polynomial-time decoding. \n\n* Shows that having the capped query with cap size of alpha=\\sqrt{k} allows the shortest-possible query complexity of size k\\polylog n.\n\n* Provides a lower bound demonstrating the optimality of the capped quantitative query with cap size of alpha=\\sqrt{k}.\n\nWeakness:\n\n* Motivation of group testing with (capped) quantitative group query is somewhat missing. Group testing with beeping has been known to be prevalent in practical applications due to its simple binary output, but group testing with (capped) quantitative group query due is less motivated due to its complexity (since it requires more than a binary bit per query). Also, for a fair comparison of effectiveness of the capped quantitative group query, the sample complexity might need to be normalized by the number of information bits per query answer for the quantitative group query.\n\n* The query construction complexity is poly(n) due to the complexity of disperser. Since the decoding requires only poly(k\\log n) complexity, the main computational overhead comes from the query construction. Any suggestion to improve this time complexity?\n\n* The query construction is based on techniques such as selectors-under-interference and strong-selectors-under-interference as well as dispersers and balanced IDs, of which the construction techniques are from [42], [44], [51]. It is unclear whether the construction directly follows from those previous results or there is some originality in the query construction part from this work. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3a7TVMBnE-L", "reviewer": "Reviewer_gTi4", "summary": "The goal in group testing is to identify a subset $K$ of $k$ elements from a universe $S$ of $n>k$ elements using queries. The queries considered in the paper are defined as the min between the size of the intersection of the query set $Q$ with $K$ and a parameter $\\alpha$. The paper restricts the attention to deterministic non-adaptive algorithms. Prior work had considered the special cases $\\alpha=1$ or $\\alpha=k$ and gave algorithms with query complexity $k^2\\log n$. The paper improves the dependence on $k$ by removing the square in the second case. It also works for the remaining range $1 \\leq \\alpha<k$ that had not been considered in prior work, matching the known upper bound for the case $\\alpha=1$. The techniques for these upper bounds involve using strong selectors under interference (based on the prior work’s notion of disperses) and a strengthening of Round-Robin query systems. The paper complements the upper bounds with a lower bound, showing that the query complexity is optimal up to polylog factors. Finally, applications of main result regarding GT on multisets, online maintenance of dynamically changing graphs and private parallel information retrieval are briefly presented and discussed in Appendix.", "questions": "The points made in the paper regarding the completion of our understanding of deterministic non-adaptive GT from a theoretical viewpoint are clear. Without diminishing these contributions, there are some questions that come to mind:\n\n* The upper bounds improve the dependence on $k$ in the query complexity but incur higher powers of $\\log(n)$. Given that in practical scenarios we care about the number of queries made as an absolute number and even constant factors in query complexity matter (having to buy 5x COVID tests does matter) is there more empirical evidence to believe that the algorithm will outperform the previous ones in terms of number of queries made?\n\n* Can you give some more comments on the benefits of having deterministic algorithms instead of randomized?\n", "limitations": "-", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Group testing is a problem that has been a topic of a long line of research. Its motivation by the concrete real-world applications relevant to the COVID-19 pandemic add to the significance of the problem. Therefore, the results of this paper are relevant to the theoretical CS community as well as being potentially useful in practical scenarios.\n\nThe writing is acceptable but with room for improvement. Overall, I found the style of writing to be dense and at parts hard to follow due to lack of intuition. Some more specific comments regarding Introduction:\n* lines 52-56: At some points the presentation does not feel precise. The “gap” refers to the one between upper and lower bounds in the table? What exactly is the fault-tolerance interpretation of line 56?\n* lines 67-74: It would be more useful to have a high-level sketch of the approach while explaining these concepts since just mentioning them does not provide much information to the new reader.\n* Section 4 feels a bit dense.\n \nI am not an expert in the topic/prior work. That being said, the arguments of the paper seem to require a certain degree of originality. To the extent that I checked the proofs I have not found issues on correctness.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept