Twenty questions with random error
information extractionmachine learningmultiuser information theoryonline learningquestion answeringShannon theorystatistical learning theorystatistical signal processing
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Learning and adaptive systems in artificial intelligence (68T05) 2-person games (91A05) Rationality and learning in game theory (91A26) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Information theory (general) (94A15) Measures of information, entropy (94A17)
This fascinating monograph studies a modern version of the so called ``Twenty questions game. \N\NThe game itself is defined between two players and starts from a player named an oracle, who privately thinks of a secret. The other player, called the questioner, tries to guess the secret by querying the oracle with at most twenty questions having Yes/No answers. The players are assumed to be honest and lying is prohibited.\N\NThe Twenty Questions game has an interesting history traced back as far as ancient Rome and Greece with numerous mathematical interpretations since then. For example, one modern mathematical formulation is guessing an integer from a finite set, where the oracle could lie either randomly to each question or lie to a finite number of questions. Remarkably, many modern mathematical studies and interpretations of this game motivates several current important applications for example in communications, machine learning; and computer vision. \N\NThe authors address numerous new theoretical interpretations of this game (with random error) as well as numerous new interdisciplinary applications both theoretically and numerically. \N\NThe monograph is a well-rounded and an extremely solid and mathematically interesting contribution to the literature. It is well written with open research problems and an excellent set of references.
- A coding scheme for additive noise channels with feedback--I: No bandwidth constraint
- A halfliar's game
- A Mathematical Theory of Communication
- A Second-Order Achievable Rate Region for Gaussian Multi-Access Channels via a Central Limit Theorem for Functions
- An almost optimal algorithm for unbounded searching
- An information-spectrum approach to capacity theorems for the general multiple-access channel
- Asymptotic Estimates in Information Theory with Non-Vanishing Error Probabilities
- Asymptotic performance of a modified Schalkwijk-Barron scheme for channels with noiseless feedback (Corresp.)
- Boolean Compressed Sensing and Noisy Group Testing
- Bounds on Variance for Unimodal Distributions
- Channel Coding Rate in the Finite Blocklength Regime
- Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels
- Coding with noiseless feedback
- Coding With Noiseless Feedback Over the Z-Channel
- Collaborative 20 Questions for Target Localization
- Contextual Search in the Presence of Adversarial Corruptions
- Exponential Strong Converse for Content Identification With Lossy Recovery
- Extrinsic Jensen–Shannon Divergence: Applications to Variable-Length Coding
- Fault-tolerant search algorithms. Reliable computation with unreliable information
- Feedback in the Non-Asymptotic Regime
- Finite Blocklength Lossy Source Coding for Discrete Memoryless Sources
- Group testing: an information theory perspective
- scientific article; zbMATH DE number 1003301 (Why is no real title available?)
- scientific article; zbMATH DE number 3513625 (Why is no real title available?)
- scientific article; zbMATH DE number 3547240 (Why is no real title available?)
- scientific article; zbMATH DE number 3555863 (Why is no real title available?)
- scientific article; zbMATH DE number 638691 (Why is no real title available?)
- scientific article; zbMATH DE number 1821199 (Why is no real title available?)
- scientific article; zbMATH DE number 3205803 (Why is no real title available?)
- scientific article; zbMATH DE number 3213251 (Why is no real title available?)
- scientific article; zbMATH DE number 3251924 (Why is no real title available?)
- scientific article; zbMATH DE number 3282350 (Why is no real title available?)
- scientific article; zbMATH DE number 3043546 (Why is no real title available?)
- scientific article; zbMATH DE number 7758315 (Why is no real title available?)
- Individual Testing Is Optimal for Nonadaptive Group Testing in the Linear Regime
- Information Spectrum Approach to Second-Order Coding Rate in Channel Coding
- Information theory. Coding theorems for discrete memoryless systems
- Least adaptive optimal search with unreliable tests
- Lossy Joint Source-Channel Coding in the Finite Blocklength Regime
- Low Complexity Sequential Search With Size-Dependent Measurement Noise
- Near-Optimal Sparsity-Constrained Group Testing: Improved Bounds and Algorithms
- Network information theory
- Noisy Adaptive Group Testing: Bounds and Algorithms
- On Decentralized Estimation With Active Queries
- On using noisy feedback in a Gaussian channel
- Optimal Feedback Communication Via Posterior Matching
- Optimal strategies against a liar
- Perfect two-fault tolerant search with minimum adaptiveness
- Performance Bounds for Group Testing With Doubly-Regular Designs
- Performance of Group Testing Algorithms With Near-Constant Tests Per Item
- Phase transitions in group testing
- Playing Guess Who with your kids: code-word strategy against adversaries
- Private sequential learning
- Probability with Martingales
- Random Access Channel Coding in the Finite Blocklength Regime
- Resolution Limits for the Noisy Non-Adaptive 20 Questions Problem
- Resolution limits of non-adaptive 20 questions search for a moving target
- Resolution Limits of Non-Adaptive 20 Questions Search for Multiple Targets
- Searching games with errors -- fifty years of coping with liars
- Searching with known error probability
- Searching with lies
- Searching with lies under error cost constraints
- Searching With Measurement Dependent Noise
- Second-Order Coding Rates for Channels With State
- Sequential transmission using noiseless feedback
- The Accuracy of the Gaussian Approximation to the Sum of Independent Variates
- The capacity of the white Gaussian multiple access channel with feedback
- The Dispersion of Nearest-Neighbor Decoding for Additive Non-Gaussian Channels
- The liar game over an arbitrary channel
- The method of types [information theory]
- The random coding bound is tight for the average code (Corresp.)
- The Two-Batch Liar Game over an Arbitrary Channel
- Twenty questions with noise: Bayes optimal policies for entropy loss
- Two Batch Search With Lie Cost
- Two-Stage Coding Over the Z-Channel
- Unequal Error Protection Querying Policies for the Noisy 20 Questions Problem
- Variable-length sparse feedback codes for point-to-point, multiple access, and random access channels
This page was built for publication: Twenty questions with random error
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6985454)
