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.
Several other noisy computational models have been investigated. Sherstov @cite_28 , showed an optimal (in terms of degree) approximation polynomial that is robust to noise. Gacs and Gal @cite_20 , proved a lower bound on the number of gates in a noise resistant circuit. These works, as well as others, have more computational complexity theory flavour than the FRAM model, and treat different computational models from the FRAM model.
@cite_28 @cite_20
2059242764 2107895738
A basic question in any computational model is how to reliably compute a given function when the inputs or intermediate computations are subject to noise at a constant rate. Ideally, one would like to use at most a constant factor more resources compared to the noise-free case. This question has been studied for decision trees, circuits, automata, data structures, broadcast networks, communication protocols, and other models. (2003) posed the noisy computation problem for real polynomials. We give a complete solution to this problem. For any polynomial p: 0,1 n->[-1,1], we construct a polynomial probust:Rn->R of degree O(deg p+log(1 e)) that epsilon-approximates p and is robust to noise in the inputs: |p(x)-probust(x+δ)| It is proved that the reliable computation of any Boolean function with, sensitivity s requires Omega (s log s) gates if the gates of the circuit fail independently with a fixed positive probability. The Omega (s log s) bound holds even if s is the block sensitivity instead of the sensitivity of the Boolean function. Some open problems are mentioned. >