Article ID Journal Published Year Pages File Type
4647146 Discrete Mathematics 2015 7 Pages PDF
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
, , , ,