Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647146 | Discrete Mathematics | 2015 | 7 Pages |
Abstract
We study the problem of using binary questions to identify a single truth teller from a collection of pp players, at most ℓℓ of whom may lie. Our focus is on trying to solve the problem using ℓℓ (or slightly more than ℓℓ) questions, which is the fewest feasible number of questions. We also obtain a randomized solution for instances of the problem that are not possible to solve deterministically.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Gilad Braunschvig, Alon Brutzkus, David Peleg, Adam Sealfon,