Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6876008 | Theoretical Computer Science | 2015 | 9 Pages |
Abstract
We conclude that if the additive noise is Gaussian, then the runtime on the noisy case, for an adapted algorithm using resamplings, is similar to the runtime on the noise-free case: we incur only an extra logarithmic factor. If the noise is non-Gaussian but with finite variance, then the total runtime of the noisy case is quadratic in function of the runtime on the noise-free case.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Youhei Akimoto, Sandra Astete-Morales, Olivier Teytaud,