TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 21.11.2013

isti-logo

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.

Date
Speaker
Location
Language
21.11.2013 16:15
Nimrod Talmon
TEL 512
english

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe