Searching with known error probability

DOI10.1016/0304-3975(89)90077-7zbMath0664.68062OpenAlexW2131306093WikidataQ56039268 ScholiaQ56039268MaRDI QIDQ1115619

Andrzej Pelc

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90077-7

zbMATH Keywords

continuous searchdiscret searchinteractive searching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items (23)

Binary search with errors and variable cost queries ⋮ A note on broadcasting with linearly bounded transmission faults in constant degree networks ⋮ Three Thresholds for a Liar ⋮ Product logic and probabilistic Ulam games ⋮ Broadcasting with linearly bounded transmission faults ⋮ External-memory sorting with comparison errors ⋮ Designing reliable algorithms in unreliable memories ⋮ Optimal strategies against a liar ⋮ Finding the maximum and minimum ⋮ The Rényi-Ulam games and many-valued logics ⋮ On sorting in the presence of erroneous information ⋮ Rényi-Ulam Game Semantics for Product Logic and for the Logic of Cancellative Hoops ⋮ Estimation of distributions involving unobservable events: the case of optimal search with unknown target distributions ⋮ Searching games with errors -- fifty years of coping with liars ⋮ Sorting and searching in faulty memories ⋮ The price of resiliency: a case study on sorting with memory faults ⋮ Ulam's searching game with two lies ⋮ Probabilistic Bisection Converges Almost as Quickly as Stochastic Approximation ⋮ Searching with a forbidden lie pattern in responses ⋮ Group testing with unreliable tests ⋮ Efficient broadcasting with linearly bounded faults ⋮ Approximate minimum selection with unreliable comparisons ⋮ Playing by searching: Two strategies against a linearly bounded liar

Cites Work

• Coping with known patterns of lies in a search game
• Solution of Ulam's problem on searching with a lie
• Coping with errors in binary search procedures
• An almost optimal algorithm for unbounded searching
• Guess a Number-with Lying
• On the theory of random search
• A class of simple and optimal strategies for block coding on the binary symmetric channel with noiseless feedback

This page was built for publication: Searching with known error probability