Name
Abstract | ||
|---|---|---|
We study the problem of using binary questions to identify a single truth teller from a collection of p 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.disc.2015.01.017 | Discrete Mathematics |
Keywords | Field | DocType |
knights and knaves,searching with errors | Discrete mathematics,Algorithm,Calculus,Mathematics,Knights and Knaves,Binary number | Journal |
Volume | Issue | ISSN |
338 | 8 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gilad Braunschvig | 1 | 5 | 1.17 |
| Alon Brutzkus | 2 | 0 | 0.34 |
| David Peleg | 3 | 6662 | 824.19 |
| Adam Sealfon | 4 | 5 | 2.44 |