Fault-tolerant search algorithms. Reliable computation with unreliable information

DOI10.1007/978-3-642-17327-1zbMath1295.68006OpenAlexW2478356874MaRDI QIDQ625104

Ferdinando Cicalese

Publication date: 14 February 2011

Published in: Monographs in Theoretical Computer Science. An EATCS Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-17327-1

zbMATH Keywords

learninggroup testingRényi-Ulam gamememory faultsadaptive fault-tolerant searchcommunication with feedbackdelays and time-outsresilient search

Mathematics Subject Classification ID

Searching and sorting (68P10) Algorithms in computer science (68Wxx) Applications of game theory (91A80) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Theory of error-correcting codes and error-detecting codes (94Bxx)

Related Items (25)

Coding with noiseless feedback ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Optimal Dislocation with Persistent Errors in Subquadratic Time ⋮ Recurring Comparison Faults: Sorting and Finding the Minimum ⋮ Search for a moving element with the minimum total cardinality of tests ⋮ Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees ⋮ Correcting a single error in feedback channels ⋮ Bounds for the capacity error function for unidirectional channels with noiseless feedback ⋮ Decoding Genomic Information ⋮ Optimal dislocation with persistent errors in subquadratic time ⋮ The Rényi-Ulam games and many-valued logics ⋮ A simple solution to Ulam's liar game with one lie ⋮ Interval group testing for consecutive positives ⋮ Unnamed Item ⋮ Searching games with errors -- fifty years of coping with liars ⋮ Least adaptive optimal search with unreliable tests ⋮ The solution space of sorting with recurring comparison faults ⋮ Rényi-Berlekamp-Ulam searching game with bi-interval queries and two lies ⋮ On the multi-interval Ulam-Rényi game: for 3 lies 4 intervals suffice ⋮ A Combinatorial Model of Two-Sided Search ⋮ Resilient Dictionaries for Randomly Unreliable Memory ⋮ The Solution Space of Sorting with Recurring Comparison Faults ⋮ Approximate minimum selection with unreliable comparisons ⋮ Truth tellers and liars with fewer questions ⋮ Sorting with Recurrent Comparison Errors

This page was built for publication: Fault-tolerant search algorithms. Reliable computation with unreliable information