Comparison-based search in the presence of errors

DOI10.1145/167088.167129zbMath1310.68070OpenAlexW2062563944MaRDI QIDQ5248479

S. Rao Kosaraju, Ryan S. Borgstrom

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167129

Mathematics Subject Classification ID

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

Related Items (18)

On-line learning of rectangles and unions of rectangles ⋮ Perfect minimally adaptive \(q\)-ary search with unreliable tests ⋮ Designing reliable algorithms in unreliable memories ⋮ Optimal strategies against a liar ⋮ Searching a Tree with Permanently Noisy Advice ⋮ Finding the maximum and minimum ⋮ Resilient dynamic programming ⋮ Searching games with errors -- fifty years of coping with liars ⋮ Least adaptive optimal search with unreliable tests ⋮ Sorting and searching in faulty memories ⋮ The price of resiliency: a case study on sorting with memory faults ⋮ Error-Correcting Tournaments ⋮ 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 ⋮ 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

This page was built for publication: Comparison-based search in the presence of errors