Three Thresholds for a Liar

DOI10.1017/S0963548300000080zbMath0801.90127DBLPjournals/cpc/SpencerW92WikidataQ56389431 ScholiaQ56389431MaRDI QIDQ4291186

Peter M. Winkler, J. H. Spencer

Publication date: 5 May 1994

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

threshold valuetwenty questions

Mathematics Subject Classification ID

2-person games (91A05)

Related Items (11)

Exact learning from an honest teacher that answers membership queries ⋮ Perfect strategies for the Ulam-Rényi game with multi-interval questions ⋮ An algorithm for ``Ulam's Game and its application to error correcting codes ⋮ Dealing with Liars: Misbehavior Identification via Rényi-Ulam Games ⋮ Finding the maximum and minimum ⋮ How to Read a Randomly Mixed Up Message ⋮ The Magnus-Derek game ⋮ Searching games with errors -- fifty years of coping with liars ⋮ Least adaptive optimal search with unreliable tests ⋮ Reconstructing a recurrent random environment from a single trajectory of a random walk in random environment with errors ⋮ Playing by searching: Two strategies against a linearly bounded liar

Cites Work

• Unnamed Item
• Balancing vectors in the max norm
• Solution of Ulam's problem on searching with a lie
• Searching with known error probability
• Coping with errors in binary search procedures
• Guess a Number-with Lying
• ON EVALUATING BOOLEAN FUNCTIONS WITH UNRELIABLE TESTS

This page was built for publication: Three Thresholds for a Liar