TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 21.11.2013


Page Content

to Navigation

Selection in the Presence of Memory Faults

Nimrod Talmon (TU Berlin)

The selection problem, where one wishes to locate the k-th smallest element in an unsorted array of size n, is one of the basic problems studied in computer science. The main focus of this talk 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 in the talk is a faulty variant of the RAM model (abbreviated as FRAM), which was introduced by Finocchi and Italiano (STOC '04). In this model, the content of memory cells might get corrupted adversarially during the execution, and the algorithm is given an upper bound delta on the number of corruptions that may occur. The main result that will be discussed in the talk 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 delta.

21.11.2013 16:15
Nimrod Talmon
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe