• Images
• Videos
• Documents
• Books
• Articles

Concrete examples

The following 6 × 8 {\displaystyle 6\times 8} matrix is 2-separable, because each pair of columns has a distinct sum. For example, the boolean sum (that is, the bitwise OR) of the first two columns is 110000 ∨ 001100 = 111100 {\displaystyle 110000\lor 001100=111100} ; that sum is not attainable as the sum of any other pair of columns in the matrix.

However, this matrix is not 3-separable, because the sum of columns 1, 2, and 3 (namely 111111 {\displaystyle 111111} ) equals the sum of columns 1, 4, and 5.

This matrix is also not 2 ¯ {\displaystyle {\overline {2}}} -separable, because the sum of columns 1 and 8 (namely 110000 {\displaystyle 110000} ) equals the sum of column 1 alone. In fact, no matrix with an all-zero column can possibly be d ¯ {\displaystyle {\overline {d}}} -separable for any d ≥ 1 {\displaystyle d\geq 1} .

[ 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 0 0 0 0 1 1 0 0 1 0 ] {\displaystyle \quad \left[{\begin{array}{cccccccc}1&0&0&1&1&0&0&0\\1&0&0&0&0&1&1&0\\0&1&0&1&0&1&0&0\\0&1&0&0&1&0&1&0\\0&0&1&0&1&1&0&0\\0&0&1&1&0&0&1&0\\\end{array}}\right]}

The following 6 × 4 {\displaystyle 6\times 4} matrix is 3 ¯ {\displaystyle {\overline {3}}} -separable (and thus 2-disjunct) but not 3-disjunct.

[ 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 ] {\displaystyle \quad \left[{\begin{array}{cccc}1&0&0&1\\1&0&1&0\\0&1&1&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{array}}\right]}

There are 15 possible ways to choose 3-or-fewer columns from this matrix, and each choice leads to a different boolean sum:

However, the sum of columns 2, 3, and 4 (namely 111111 {\displaystyle 111111} ) is a superset of column 1 (namely 110000 {\displaystyle 110000} ), which means that this matrix is not 3-disjunct.

Application of d-separability to group testing

Main article: Group testing

The non-adaptive group testing problem postulates that we have a test which can tell us, for any set of items, whether that set contains a defective item. We are asked to come up with a series of groupings that can exactly identify all the defective items in a batch of n total items, some d of which are defective.

A d {\displaystyle d} -separable matrix with t {\displaystyle t} rows and n {\displaystyle n} columns concisely describes how to use t tests to find the defective items in a batch of n, where the number of defective items is known to be exactly d.

A d {\displaystyle d} -disjunct matrix (or, more generally, any d ¯ {\displaystyle {\overline {d}}} -separable matrix) with t {\displaystyle t} rows and n {\displaystyle n} columns concisely describes how to use t tests to find the defective items in a batch of n, where the number of defective items is known to be no more than d.

Practical concerns and published results

For a given n and d, the number of rows t in the smallest d-separable t × n {\displaystyle t\times n} matrix may (according to current knowledge) be smaller than the number of rows t in the smallest d-disjunct t × n {\displaystyle t\times n} matrix, but in asymptotically they are within a constant factor of each other.⁷ Additionally, if the matrix is to be used for practical testing, some algorithm is needed that can "decode" a test result (that is, a boolean sum such as 111100 {\displaystyle 111100} ) into the indices of the defective items (that is, the unique set of columns that produce that boolean sum). For arbitrary d-disjunct matrices, polynomial-time decoding algorithms are known; the naïve algorithm is O ( n t ) {\displaystyle O(nt)} .⁸ For arbitrary d-separable but non-d-disjunct matrices, the best known decoding algorithms are exponential-time.⁹

Porat and Rothschild (2008) present a deterministic O ( n t ) {\displaystyle O(nt)} -time algorithm for constructing a d-disjoint matrix with n columns and Θ ( d 2 ln ⁡ n ) {\displaystyle \Theta (d^{2}\ln n)} rows.¹⁰

See also

• Group testing
• Concatenated code
• Compressed sensing

Further reading

• Atri Rudra's book on Error Correcting Codes: Combinatorics, Algorithms, and Applications (Spring 201), Chapter 17 Archived 2015-04-02 at the Wayback Machine
• Dýachkov, A. G., & Rykov, V. V. (1982). Bounds on the length of disjunctive codes. Problemy Peredachi Informatsii [Problems of Information Transmission], 18(3), 7–13.
• Dýachkov, A. G., Rashad, A. M., & Rykov, V. V. (1989). Superimposed distance codes. Problemy Upravlenija i Teorii Informacii [Problems of Control and Information Theory], 18(4), 237–250.
• Füredi, Zoltán (1996). "On r-Cover-free Families". Journal of Combinatorial Theory. Series A. 73 (1): 172–173. doi:10.1006/jcta.1996.0012.

References

1. De Bonis, Annalisa; Vaccaro, Ugo (2003). "Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels". Theoretical Computer Science. 306 (1–3): 223–243. doi:10.1016/S0304-3975(03)00281-0. MR 2000175. /wiki/Doi_(identifier) ↩

2. Paul Erdős; Péter Frankl; Zoltán Füredi (1985). "Families of finite sets in which no set is covered by the union of r others" (PDF). Israel Journal of Mathematics. 51 (1–2): 79–89. doi:10.1007/BF02772959. ISSN 0021-2172. /wiki/Paul_Erd%C5%91s ↩

3. Hong-Bin Chen; Frank Hwang (2006-12-21). "Exploring the missing link among d-separable, d-separable and d-disjunct matrices". Discrete Applied Mathematics. 155 (5): 662–664. CiteSeerX 10.1.1.848.5161. doi:10.1016/j.dam.2006.10.009. MR 2303978. https://doi.org/10.1016%2Fj.dam.2006.10.009 ↩

4. Hong-Bin Chen; Frank Hwang (2006-12-21). "Exploring the missing link among d-separable, d-separable and d-disjunct matrices". Discrete Applied Mathematics. 155 (5): 662–664. CiteSeerX 10.1.1.848.5161. doi:10.1016/j.dam.2006.10.009. MR 2303978. https://doi.org/10.1016%2Fj.dam.2006.10.009 ↩

5. Hong-Bin Chen; Frank Hwang (2006-12-21). "Exploring the missing link among d-separable, d-separable and d-disjunct matrices". Discrete Applied Mathematics. 155 (5): 662–664. CiteSeerX 10.1.1.848.5161. doi:10.1016/j.dam.2006.10.009. MR 2303978. https://doi.org/10.1016%2Fj.dam.2006.10.009 ↩

6. Hong-Bin Chen; Frank Hwang (2006-12-21). "Exploring the missing link among d-separable, d-separable and d-disjunct matrices". Discrete Applied Mathematics. 155 (5): 662–664. CiteSeerX 10.1.1.848.5161. doi:10.1016/j.dam.2006.10.009. MR 2303978. https://doi.org/10.1016%2Fj.dam.2006.10.009 ↩

7. Hong-Bin Chen; Frank Hwang (2006-12-21). "Exploring the missing link among d-separable, d-separable and d-disjunct matrices". Discrete Applied Mathematics. 155 (5): 662–664. CiteSeerX 10.1.1.848.5161. doi:10.1016/j.dam.2006.10.009. MR 2303978. https://doi.org/10.1016%2Fj.dam.2006.10.009 ↩

8. Piotr Indyk; Hung Q. Ngo; Atri Rudra (2010). "Efficiently Decodable Non-adaptive Group Testing". Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA). hdl:1721.1/63167. ISSN 1071-9040. /wiki/Piotr_Indyk ↩

9. Hong-Bin Chen; Frank Hwang (2006-12-21). "Exploring the missing link among d-separable, d-separable and d-disjunct matrices". Discrete Applied Mathematics. 155 (5): 662–664. CiteSeerX 10.1.1.848.5161. doi:10.1016/j.dam.2006.10.009. MR 2303978. https://doi.org/10.1016%2Fj.dam.2006.10.009 ↩

10. Ely Porat; Amir Rothschild (2008). "Explicit Non-Adaptive Combinatorial Group Testing Schemes". Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP): 748–759. arXiv:0712.3876. Bibcode:2007arXiv0712.3876P. /wiki/ArXiv_(identifier) ↩