Searching with lies

DOI10.1006/jcta.1996.0036zbMath0846.90149OpenAlexW2056717988MaRDI QIDQ1913996

Martin Aigner

Publication date: 9 July 1996

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcta.1996.0036

zbMATH Keywords

\(q\)-ary search process1-error correcting codes

Mathematics Subject Classification ID

Searching and sorting (68P10) Combinatorial games (91A46)

Related Items

Coding with noiseless feedback ⋮ \(Q\)-ary search with one Lie and bi-interval queries ⋮ Minimum average-case queries of \(q+1\)-ary search game with small sets ⋮ On a hyperplane arrangement problem and tighter analysis of an error-tolerant pooling design ⋮ \(Q\)-ary Rényi-Ulam pathological liar game with one lie ⋮ Perfect minimally adaptive \(q\)-ary search with unreliable tests ⋮ Optimal strategies against a liar ⋮ Pooling designs associated with unitary space and ratio efficiency comparison ⋮ Searching games with errors -- fifty years of coping with liars ⋮ Least adaptive optimal search with unreliable tests ⋮ Rényi-Berlekamp-Ulam searching game with bi-interval queries and two lies ⋮ Minimum number of queries for an adaptive liar search game with small sets ⋮ Perfect two-fault tolerant search with minimum adaptiveness ⋮ An improved heuristic for the ``Ulam-Rényi game ⋮ An efficient noisy binary search in graphs via Median approximation ⋮ On error correction with errors in both the channel and syndrome