2026-07-31T03:20:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13540 2024-03-06T10:52:16Z ddc:004 open_access

The Entropy of Lies: Playing Twenty Questions with a Liar Dagan, Yuval Filmus, Yuval Kane, Daniel Moran, Shay entropy twenty questions algorithms sorting "Twenty questions" is a guessing game played by two players: Bob thinks of an integer between 1 and n, and Alice’s goal is to recover it using a minimal number of Yes/No questions. Shannon’s entropy has a natural interpretation in this context. It characterizes the average number of questions used by an optimal strategy in the distributional variant of the game: let μ be a distribution over [n], then the average number of questions used by an optimal strategy that recovers x∼ μ is between H(μ) and H(μ)+1. We consider an extension of this game where at most k questions can be answered falsely. We extend the classical result by showing that an optimal strategy uses roughly H(μ) + k H_2(μ) questions, where H_2(μ) = ∑_x μ(x)log log 1/μ(x). This also generalizes a result by Rivest et al. (1980) for the uniform distribution. Moreover, we design near optimal strategies that only use comparison queries of the form "x ≤ c?" for c ∈ [n]. The usage of comparison queries lends itself naturally to the context of sorting, where we derive sorting algorithms in the presence of adversarial noise. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuval Dagan and Yuval Filmus and Daniel Kane and Shay Moran 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.1 urn:nbn:de:0030-drops-135400 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.1 eng https://creativecommons.org/licenses/by/3.0/legalcode