Randomized algorithms: a system-level, poly-time analysis of robust computation

Provides a methodology for analyzing the performance degradation of a computation once it has been affected by perturbations. The suggested methodology, by relaxing all assumptions made in the related literature, provides design guidelines for the subsequent implementation of complex computations in physical devices. Implementation issues, such as finite precision representation, fluctuations of the production parameters and aging effects, can be studied directly at the system level, independent of any technological aspect and quantization technique. Only the behavioral description of the computational flow, which is assumed to be Lebesgue-measurable, and the architecture to be investigated are needed. The suggested analysis is based on the theory of randomized algorithms, which transforms the computationally intractable problem of robustness investigation into a polynomial-time algorithm by resorting to probability