The selection problem, where one wishes to locate the @math smallest element in an unsorted array of size @math , is one of the basic problems studied in computer science. The main focus of this work is designing algorithms for solving the selection problem in the presence of memory faults. These can happen as the result of cosmic rays, alpha particles, or hardware failures. Specifically, the computational model assumed here is a faulty variant of the RAM model (abbreviated as FRAM), which was introduced by Finocchi and Italiano. In this model, the content of memory cells might get corrupted adversarially during the execution, and the algorithm is given an upper bound @math on the number of corruptions that may occur. The main contribution of this work is a deterministic resilient selection algorithm with optimal O(n) worst-case running time. Interestingly, the running time does not depend on the number of faults, and the algorithm does not need to know @math . The aforementioned resilient selection algorithm can be used to improve the complexity bounds for resilient @math -d trees developed by Gieseke, Moruz and Vahrenhold. Specifically, the time complexity for constructing a @math -d tree is improved from @math to @math . Besides the deterministic algorithm, a randomized resilient selection algorithm is developed, which is simpler than the deterministic one, and has @math expected time complexity and O(1) space complexity (i.e., is in-place). This algorithm is used to develop the first resilient sorting algorithm that is in-place and achieves optimal @math expected running time.
In this model, the algorithm can access the data only through a noisy oracle. The algorithm queries the oracle and can possibly get a faulty answer (i.e., a lie). An upper bound on the number of these lies or a probability of a lie is assumed. See, e.g., @cite_10 and @cite_17 . The data itself cannot get corrupted, therefore, in this model, query replication strategies can be exploited, in contrast to the FRAM model.
@cite_10 @cite_17
2038435918 2069363808
This paper studies the depth of noisy decision trees in which each node gives the wrong answer with some constant probability. In the noisy Boolean decision tree model, tight bounds are given on the number of queries to input variables required to compute threshold functions, the parity function and symmetric functions. In the noisy comparison tree model, tight bounds are given on the number of noisy comparisons for searching, sorting, selection and merging. The paper also studies parallel selection and sorting with noisy comparisons, giving tight bounds for several problems. Motivated by the problem of searching in the presence of adversarial errors, we consider a version of the game “Twenty Questions” played on the set 0,…,N-1 where the player giving answers may lie in her answers. The questioner is allowed Q questions and the responder may lie in upto [ rQ ] of the answers, for some fixed and previously known fraction r . Under three different models of this game and for two different question classes, we give precise conditions (i.e. tight bounds on r and, in most cases, optimal bounds on Q under which the questioner has a winning strategy in the game.