Coping with errors in binary search procedures

DOI10.1016/0022-0000(80)90014-8zbMath0443.68043OpenAlexW2048175848WikidataQ59701061 ScholiaQ59701061MaRDI QIDQ1144379

Ronald L. Rivest, J. H. Spencer, Albert R. Meyer, Daniel J. Kleitman, Klaus Winkelmann

Publication date: 1980

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(80)90014-8

zbMATH Keywords

binary searchcoping with errors

Mathematics Subject Classification ID

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

Related Items (50)

A survey of information-based complexity ⋮ Binary search with errors and variable cost queries ⋮ Lie patterns in search procedures ⋮ Solution of Ulam's problem on searching with a lie ⋮ Search problems: One, two or many rounds ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Prefix search with a lie ⋮ On the complexity of function learning ⋮ Three Thresholds for a Liar ⋮ Continuous guessing games with two secret numbers ⋮ Searching with known error probability ⋮ Unnamed Item ⋮ Detecting errors in searching games ⋮ Ulam's searching game with lies ⋮ Operations research applications of dichotomous search ⋮ Reliable minimum finding comparator networks ⋮ On the Rényi-Ulam game with restricted size queries ⋮ Coping with errors in binary search procedures ⋮ Correcting a single error in feedback channels ⋮ Designing reliable algorithms in unreliable memories ⋮ Perfect strategies for the Ulam-Rényi game with multi-interval questions ⋮ Optimal strategies against a liar ⋮ Ulam's searching game with a fixed number of lies ⋮ Solution of Ulam's problem on binary search with three lies ⋮ An algorithm for ``Ulam's Game and its application to error correcting codes ⋮ Dealing with Liars: Misbehavior Identification via Rényi-Ulam Games ⋮ The lying oracle game with a biased coin ⋮ Finding the maximum and minimum ⋮ A simple solution to Ulam's liar game with one lie ⋮ Searching with lies: The Ulam problem ⋮ On sorting in the presence of erroneous information ⋮ The infinite duration lying oracle game ⋮ A PATH GUESSING GAME WITH WAGERING ⋮ Unnamed Item ⋮ Contract scheduling with predictions ⋮ Searching games with errors -- fifty years of coping with liars ⋮ Sorting and searching in faulty memories ⋮ Ulam's searching game with three lies ⋮ The price of resiliency: a case study on sorting with memory faults ⋮ Ulam's searching game with two lies ⋮ Searching with a forbidden lie pattern in responses ⋮ Group testing with unreliable tests ⋮ Approximate minimum selection with unreliable comparisons ⋮ Optimal resilient sorting and searching in the presence of memory faults ⋮ Perfect two-fault tolerant search with minimum adaptiveness ⋮ Coping with known patterns of lies in a search game ⋮ Playing by searching: Two strategies against a linearly bounded liar ⋮ 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

Cites Work

• Coping with errors in binary search procedures
• A class of simple and optimal strategies for block coding on the binary symmetric channel with noiseless feedback
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Coping with errors in binary search procedures