Preface
Acknowledgments
Contents
Chapter
1 Prologue: What This Book Is About
1.1 Part I: The Basic Model
1.1.1 Adaptive vs. Non-adaptive Search
1.1.2 Q-ary Search with Lies
1.1.3 Half-Lies, Erasures and Other Types of Errors
1.1.4 Heuristics
1.2 Part II: More Models and Applications
1.2.1 Erasure Errors, Delays and Time-outs
1.2.2 Group Testing
1.2.3 Memory Faults and Resilient Search
1.2.4 A Model of Learning
1.3 Bibliographic Notes
Part I The Ulam-Rรฉnyi Game and Its Variants
Chapter
2 Fault-Tolerant Search ร la Ulam-Rรฉnyi
2.1 Introduction
2.1.1 The Binary Ulam-Rรฉnyi Game
2.2 The Volume Bound
2.3 Borderline States Satisfying the Volume Bound with Equality
2.4 The Solution of the 20 Question Game with Lies
2.5 Asymptotics for the Ulam-Rรฉnyi Problem
2.6 Heuristics for the Ulam-Rรฉnyi Problem
Algorithm 1
Algorithm 2
2.6.1 Experimental Validation of the Heuristics
2.7 Bibliographic Notes
2.8 Exercises
Chapter
3 Adaptive vs. Non-adaptive Search
3.1 Coding in a Channel with Noiseless Feedback
3.2 No Feedback Equals Error-Correcting Codes
3.3 Elements of the Theory of Error-Correcting Codes
3.3.1 Linear and Hamming Codes
3.3.2 MDS Codes and the Reed-Solomon Codes
3.3.3 Bounds on Codes
3.4 Fault-Tolerant q-ary Search and Minimum Feedback
3.4.1 Fault-Tolerant q-ary search
3.4.2 Perfect Strategies and Least Adaptiveness: M=qm
The Non-adaptive Second Batch of Questions
Shrinking the First Batch of Questions
3.4.3 Arbitrary Cardinality of the Search Space: Least Adaptive Quasi-perfect Strategies
More About Perfect Minimally Adaptive Strategies
Quasi-perfect Strategies: The Main Theorem
3.5 Some Finite Exact Results for the q-ary Adaptive Ulam-Rรฉnyi game
An Infinite Sequence of Winning States for q-ary Search
Coping with Many Lies When M=qm
3.6 Bibliographic Notes
3.7 Exercises
Chapter
4 Weighted Errors over a General Channel
4.1 Introduction
4.2 Two-Batch Search with Weighted Lies
4.3 The Lower Bound: The Winning Strategy
4.3.1 The First Batch of Questions
4.3.2 The Second Batch of Questions
4.4 The Upper Bound
4.5 Other Noise Models: Unidirectional Errors
4.6 Bibliographic Notes
4.7 Exercises
Chapter
5 Variations on a Theme of Ulam and Rรฉnyi: More Types of Questions and Lies
5.1 Comparison-Based Search: The Multiple-Interval Queries
5.2 Query Optimal Multi-interval Search with k = O(e2)
5.2.1 The Case of Two Lies: A Canonical Representation of States and 2-Interval Queries
5.2.2 About Comparison Questions
5.3 Linearly Bounded Number of Lies
5.4 Prefix-Bounded Numbers of Lies
5.5 Bibliographic Notes
5.6 Exercises
Part II Other Models
Chapter
6 Delays and Time Outs
6.1 Search with Fixed Batches of Questions and Variable Delay in Answers
6.2 Search with Variable Batches and Delays
6.3 Lost Answers and Delays
6.3.1 Extensions and Generalizations
6.3.2 The Proof of Proposition 6.1
6.3.3 Broadcast with Latency vs. Search with Delay
Broadcast in the Postal Model
Broadcast and Comparison Search Are Isomorphic Problems
6.4 Bibliographic Notes
6.5 Exercises
Chapter
7 Group Testing
7.1 Group Testing with Subset Tests
7.1.1 The (p,v,n)-super-selector
7.1.2 Approximate Group Testing
7.1.3 Bounds on the Size of a (p, v, n)-super-selector
7.2 Interval Group Testing
Sets of Queries and YES-Sets
7.2.1 Non-adaptive Fault-Tolerant Interval Group Testing
7.2.2 Two-Stage Fault-Tolerant Interval Group Testing
An Averaging Argument for Lower Bound on Two-Stage Interval Group Testing
The Averaging Argument in Use
Yes-sets and Errors
Bounds for Two-Stage Algorithms with One Positive
More Positives
More Errors
7.3 Some Typical Applications of Group Testing in Computational Biology
7.4 Bibliographic Notes
7.5 Exercises
Chapter
8 Resilient Search
8.1 The Definition of the Problem and a Lower Bound
8.2 Randomized Resilient Search
8.3 Optimal Deterministic Resilient Search
8.3.1 The Verification Procedure
8.4 Bibliographic Notes
8.5 Exercises
Chapter
9 A Model for Learning
9.1 Computational Learning
9.2 Predicting from Expert Advice
9.3 Learning in Noisy Environments
9.3.1 Rรฉnyi's Probabilistic Example
9.3.2 Learning with Negative Reinforcement
9.3.3 Supervised Learning for Online Prediction
9.4 Bibliographic Notes
9.5 Exercises
Bibliography