Ebook: Combinatorial group testing and its applications

This book analyzes in considerable generality the quantization-dequantization integral transform scheme of Weyl and Wigner, and considers several phase operator theories. It features: a thorough treatment of quantization in polar coordinates; dequantization by a new method of "motes"; a discussion of Moyal algebras; modifications of the transform method to accommodate operator orderings; a rigorous discussion of the Dieke laser model for one mode, fully quantum, in the thermodynamic limit; analysis of quantum phase theories based on the Toeplitz operator, the coherent state operator, the quantized phase space angle, and a sequence of finite rank operators Ch. 1. Introduction. 1.1. The History of Group Testing. 1.2. The Binary Tree Representation of a Group Testing Algorithm and the Information Lower Bound. 1.3. The Structure of Group Testing. 1.4. Number of Group Testing Algorithms. 1.5. A Prototype Problem and Some Basic Inequalities. 1.6. Variations of the Prototype Problem -- Ch. 2. General Algorithms. 2.1. Li's s-Stage Algorithm. 2.2. Hwang's Generalized Binary Splitting Algorithm. 2.3. The Nested Class. 2.4. (d, n) Algorithms and Merging Algorithms. 2.5. Some Practical Considerations. 2.6. An Application to Clone Screenings -- Ch. 3. Algorithms for Special Cases. 3.1. Two Disjoint Sets Each Containing Exactly One Defective. 3.2. An Application to Locating Electrical Shorts. 3.3. The 2-Defective Case. 3.4. The 3-Defective Case. 3.5. When is Individual Testing Minimax? 3.6. Identifying a Single Defective with Parallel Tests -- Ch. 4. Nonadaptive Algorithms and Binary Superimposed Codes. 4.1. The Matrix Representation. 4.2. Basic Relations and Bounds. 4.3. Constant Weight Matrices and Random Codes. 4.4. General Constructions. 4.5. Special Constructions -- Ch. 5. Multiaccess Channels and Extensions. 5.1. Multiaccess Channels. 5.2. Nonadaptive Algorithms. 5.3. Two Variations. 5.4. The k-Channel. 5.5. Quantitative Channels -- Ch. 6. Some Other Group Testing Models. 6.1. Symmetric Group Testing. 6.2. Some Additive Models. 6.3. A Maximum Model. 6.4. Some Models for d = 2 -- Ch. 7. Competitive Group Testing. 7.1. The First Competitiveness. 7.2. Bisecting. 7.3. Doubling. 7.4. Jumping. 7.5. The Second Competitiveness. 7.6. Digging. 7.7. Tight Bound -- Ch. 8. Unreliable Tests. 8.1. Ulam's Problem. 8.2. General Lower and Upper Bounds. 8.3. Linearly Bounded Lies (1). 8.4. The Chip Game. 8.5. Linearly Bounded Lies (2). 8.6. Other Restrictions on Lies -- Ch. 9. Optimal Search in One Variable. 9.1. Midpoint Strategy. 9.2. Fibonacci Search. 9.3. Minimum Root Identification -- Ch. 10. Unbounded Search. 10.1. Introduction. 10.2. Bentley-Yao Algorithms. 10.3. Search with Lies. 10.4. Unbounded Fibonacci Search -- Ch. 11. Group Testing on Graphs. 11.1. On Bipartite Graphs. 11.2. On Graphs. 11.3. On Hypergraphs. 11.4. On Trees. 11.5. Other Constraints -- Ch. 12. Membership Problems. 12.1. Examples. 12.2. Polyhedral Membership. 12.3. Boolean Formulas and Decision Trees. 12.4. Recognition of Graph Properties -- Ch. 13. Complexity Issues. 13.1. General Notions. 13.2. The Prototype Problem is in PSPACE. 13.3. Consistency. 13.4. Determinacy. 13.5. On Sample Space S(n). 13.6. Learning by Examples