{'fraction_non_alphanumeric': 0.040223997814655466, 'fraction_numerical': 0.00758041384962098, 'mean_word_length': 4.279019466474405, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Symmetric Group Testing and Superimposed Codes

We describe a generalization of the group testing problem termed symmetric group testing. Unlike in classical binary group testing, the roles played by the input symbols zero and one are"symmetric"while the outputs are drawn from a ternary alphabet. Using an information-theoretic approach, we derive sufficient and necessary conditions for the number of tests required for noise-free and noisy reconstructions. Furthermore, we extend the notion of disjunct (zero-false-drop) and separable (uniquely decipherable) codes to the case of symmetric group testing. For the new family of codes, we derive bounds on their size based on probabilistic methods, and provide construction methods based on coding theoretic ideas.


I. INTRODUCTION
Group testing is a combinatorial scheme developed for the purpose of efficient identification of infected individuals in a given pool of subjects [1]. The main idea behind the approach is that if a small number of individuals are infected, one can test the population in groups, rather than individually, thereby saving in terms of the number of tests conducted. A tested group is said to be positive if at least one of its members tests positive; otherwise, the tested group is said to be negative. Each individual from a population of size N is represented by a binary test vector (or signature) of length n, indicating in which of the n tests the individual participates. The test outcomes are represented by a vector of size n that equals the entry-wise Boolean OR function of the signatures of infected individuals. The reconstruction task consists of identifying the infected individuals based on their test signatures, using the smallest signature length n.
The work in [1] was extended in [2], where the authors proposed two coding schemes for use in information retrieval systems and for channel assignments aimed at relieving congestion in crowded communications bands. The coding schemes are now known as superimposed codes, including disjunct/zero-false-drop (D/ZFD) and separable/uniquely decipherable (S/UD) codes. For compactness, we henceforth only use the terms disjunct (D) and separable (S) to describe such codes. These two classes of superimposed codes were extensively studied -see [3]- [7] and references therein.
Superimposed codes are inherently asymmetric with respect to the elements of the input alphabet: if all tested subjects are negative (i.e., zero), the output is negative. Otherwise, for any positive number of infected test subjects, the output is positive. Consequently, a zero output carries significantly more information than an output equal to one. For many applications, including DNA pooling and other genomic and biological testing methods with low sensitivity, a test may be positive only if a sufficiently large number of subjects test positive [4]. In particular, a test outcome may be positive if and only if all subjects are infected.
A probabilistic scheme that makes the group test symmetric with respect to the all-positive and all-negative tests was first described in [8], [9]. To the best of our knowledge, these are the only two papers dealing with "symmetric" group tests, although only within a probabilistic setting where the inputs are assumed to follow a binomial distribution. In addition, the method was only studied for two extremal parameter choices, using a game-theoretic framework in which the player's strategies (i.e., reconstruction methods) are fixed and involve some form of oracle information.
A more recent approach to the problem of a nearlysymmetric group testing was described in [10]. Threshold group testing assumes that a test is positive (or negative) if more (or less) than u (or l) individuals tested are positive, where 1 ≤ l ≤ u ≤ N . A test produces an arbitrary outcome (zero or one) otherwise. The latter feature makes the testing problem highly nontrivial and substantially different from symmetric group testing (SGT).
We are concerned with describing symmetric group testing in a combinatorial setting, extending the concept of symmetry using information theoretic methods and in developing analogues of D and S codes, termed D s and S s codes. Our results include bounds on the size of the test set of symmetric group testing, construction methods for symmetric D and S codes, and efficient reconstruction algorithms in the absence and presence of errors. Bounds on the size of D s and S s codes are based on Lovász Local Lemma [11] and constructive coding theoretic arguments.
The paper is organized as follows. Section II contains a short exposition regarding symmetric group testing, while information-theoretic bounds on the number of required tests are derived in noisy and noise-free scenarios. In Section III, a generalization of SGT (termed generalized group testing) is introduced by employing a lower and upper threshold, and information theoretic bounds on the number of required tests are derived. Section IV introduces symmetric superimposed codes and contains derivations on the bounds on the size of D s and S s codes. Finally, Section V presents some techniques for constructing symmetric superimposed codes.

II. SYMMETRIC GROUP TESTING
The use of SGT was originally motivated by applications in circuit testing and chemical component analysis [8]. As an illustrative example, consider the situation where one is to test N identically designed circuits using only serial and parallel component concatenation. In the serial testing mode, one can detect if all circuits are operational. In the parallel mode, one can detect if all circuits are non-operational. If at least one circuit is operational and one is non-operational, neither of the two concatenation schemes will be operational. Detecting efficiently which of the circuits are non-operational would require a ternary output group testing scheme.
The reasons for introducing symmetric group testing with ternary outputs are twofold. The first motivation is to provide symmetry in the information content of the output symbols zero and one. Note that in standard group testing, a zero output automatically eliminates all tested subjects from further consideration, which is not the case with the symbol one. In symmetric group testing, the symbols zero and one play a symmetric role. The second motivation comes from biological applications in which the sensitivity of the measurement devices is such that it can only provide a range for the number of infected individuals in a pool: for example, the output may be "0" if less than l individuals in the test set are infected, "1" if more than u ≥ l individuals are infected, and "2" in all other cases.
Throughout the paper we use the word "positive" ("negative") to indicate that a tested subject has (does not have) a given property. For the asymmetric testing strategy, the outcome of a test is negative if all tested subjects are negative, and positive otherwise. The outcome of a symmetric test is said to be positive (denoted by "1"), inconclusive (denoted by "2"), or negative (denoted by "0"), if all the subjects tested are positive, at least one subject is positive and another one is negative, and all subjects are negative, respectively.
Let N denote the total number of test subjects, and let D denote the defective set with cardinality |D| = m. Furthermore, let X D denote the collection of codewords (or signatures) corresponding to D; note that the length of each codeword is equal to n. Also, let y ∈ {0, 1, 2} n denote the noise-free observation vector (test outcome) equal to the ternary addition of the codewords of the defective set, where ternary addition is defined as follows.
Clearly, ternary addition is commutative and associative.
Note that in general the ternary addition operator is more informative than its binary counterpart; consequently, one expects that the number of required tests in the SGT is smaller than the number of required tests in a similar asymmetric group testing (AGT) scheme. We hence focus on finding upper and lower bounds on the minimum number of tests in a SGT scheme that ensures detection of the defective set with probability of error asymptotically converging to zero.

A. Noise-free Symmetric Group Testing
In the noise-free case, the observation vector is equal to the superposition of the signatures of defectives, i.e., where "+" denotes ternary addition, and x ij stands for the signature of the j th defective subject.
Let the tests be designed independently, and let p denote the probability that a subject is part of a given test, independent of all other subjects. It was shown in [12] that for any m = o(N ), a sufficient number of tests for asymptotically achieving a probability of error equal to zero in the AGT setting is lower bounded as D denotes all ordered pairs of sets (D 1 , D 2 ) that partition the defective set, such that |D 1 | = i and |D 2 | = m−i. In the above equation, I(X D1 ; X D2 , y) stands for the mutual information between X D1 and (X D2 , y); for a single test, X Dt (where t = 1, 2) is a vector of size 1 × |D t |, with its k th entry equal to 1 if the k th defective subject in D t is in the test and 0 otherwise, while y is the outcome of the test.
Also, a necessary condition for zero error probability in AGT was shown to be of the form [12] n ≥ max By following the same steps in the proof of the above two bounds, it can be easily shown that the same sufficient and necessary conditions hold for the SGT scheme, except for the fact that the mutual information will evaluate to a different form given the change in the output alphabet. In the following Proposition, we evaluate the expressions for mutual information in (2) and (3) for SGT.

Proposition 1:
In the noise-free SGT for m ≥ 2, where |D 1 | = i, and where for any Proof: Let w j (where j = 1, 2) denote the number of ones in X Dj , or alternatively, the Hamming weight of X Dj .
Similarly, it can be shown that for AGT, In order to compare SGT and AGT, fix p and let Using the above definition, the bounds in (2) and (3) asymptotically simplify to n > log N α(m,p) and n ≥ log N α(m,p) , respectively. Also, let α A (m) and α S (m) denote the values of α(m, p) for the choice of p that minimizes the lower bounds in the AGT and SGT expressions 1 , respectively. Fig. 1 shows the behavior of these parameters with respect to m. As can be seen, for m = 2, αS(m) αA(m) = 1.5, but as m grows, this ratio converges to one.

B. Symmetric Group Testing in the Presence of Binary Additive Noise
This type of noise accounts for false alarms in the outcome of the tests. In this case, the noise vector, z, is modeled as a vector of independent identically distributed (i.i.d.) Bernoulli random variables with parameter q; the vector of noisy observations,ỹ, equals the ternary sum of the vector of noise-free observations and the noise vector, i.e.,ỹ = y + z. Note that in this model, we assume that both 0's and 1's may change to the value 2, while 2's remain unaltered in the presence of noise. This model applies whenever dilution effects may occur, since adding one positive (negative) subject may change the outcome of a negative (positive) group.

Proposition 2:
In the presence of binary additive noise, for any m ≥ 2, where w denotes the Hamming weight of X D . Using these two expressions in the definition of the mutual information completes the proof. Similarly, it can be shown that for AGT,

III. GENERALIZED GROUP TESTING
In many applications, the experiment cannot be modeled by AGT or SGT, and a more general model is required. We hence consider the generalized group testing (GGT) problem in which the outcome of a test equals 0 if the number of defectives in the corresponding pool is less than or equal to η 1 (where η 1 ≥ 0), equals 1 if the number of defectives is larger than η 2 (where η 1 ≤ η 2 ≤ m − 1), and equals 2 if the number of defectives is larger than η 1 and is less than or equal to η 2 . Note that when η 1 = η 2 = 0 GGT reduces to AGT, and when η 1 = 0 and η 2 = m − 1 GGT reduces to SGT.

Proposition 3:
In GGT, and for any i = 1, 2, · · · , m, where m ≥ 2, As before, p denotes the probability that a subject is part of a given random test.

IV. SYMMETRIC SUPERIMPOSED CODES
In this section, we introduce disjunct and separable symmetric superimposed codes for the SGT scheme. We postpone the discussion of generalized disjunct and separable codes to the full version of the paper. Definition 2: Given two ternary vectors x and y, and a ternary addition operator, we say that y is included in x if x + y = x. Definition 3: Let the addition operator be the ternary addition described in Def. 1. A code C is a symmetric m-disjunct code if for any sets of binary codewords {x 1 , x 2 , · · · , x s } and {y 1 , y 2 , · · · , y t }, the sum x 1 + x 2 + ... + x s being  included in y 1 + y 2 + ... + y t implies that {x 1 , x 2 , · · · , x s } ⊆ {y 1 , y 2 , · · · , y t }, for any s, t ≤ m.
Henceforth, we refer to m as the strength of code C and use N (m) and n(m) to denote the number of codewords (the signatures of the subjects) and their length, respectively. The rate of a superimposed code of strength m is defined as R m = log N (m) n(m) , where log stands for the logarithm base two. Whenever apparent from the context, we use N and n instead of N (m) and n(m).

A. Bounds on the Size of Symmetric Disjunct Codes
In this subsection, we derive an upper bound on the size of D s (m) codes using probabilistic methods.
then P i E i > 0, where e is the base of the natural logarithm and E i is the complement of the event E i . In other words, if (11) is satisfied, there exists a choice of N codewords that form a symmetric disjunct superimposed (n, N, m)−code, C. Note that if no codeword is included in the sum of m other codewords, then no codeword is included in the sum of any set of other codewords with cardinality smaller than m. Lemma 1: For all i one has and as n → ∞, one has Substituting p ′ into (11) and using the fact that N m+1 − .
The ratio RS(m) RA(m) is approximately equal to 2 when m = 2 and tends to 1 as m grows.

B. Bounds on the Size of Symmetric Separable Codes
In this subsection, we find an upper bound on the size of symmetric separable codes when m = 2.

V. CONSTRUCTION OF SYMMETRIC SUPERIMPOSED CODES
Due to space limitations, we only consider symmetric separable codes with m = 2 for which a construction based on coding theoretic methods is particularly simple. Comparing the above method to the construction in [2], one can see that the size of symmetric codes is twice as large as the size of asymmetric codes.