Seminario Interdipartimentale di Algoritmica
 
 

DIS - Dipartimento di Informatica e Sistemistica, via Salaria 113
C3 Room, second floor

Abstract:

We address the design of algorithms resilient to memory faults, i.e., algorithms that, despite the corruption of some memory values during their execution, are able to produce a correct output on the set of uncorrupted values. In this framework, we consider two fundamental problems: sorting and searching. In particular, we prove that any O(n log n) comparison-based sorting algorithm can tolerate at most O((n log n)^{1/2}) memory faults. Furthermore, we present one comparison-based sorting algorithm with optimal space and running time that is resilient to O((n\log n)^{1/3}) faults. We also prove polylogarithmic lower and upper bounds on fault-tolerant searching.

(Joint work with G. F. Italiano)