Skip to main content

Tight space-noise tradeoffs in computing the ergodic measure

Author(s): Braverman, Mark; Rojas, Cristóbal; Schneider, Jon

To refer to this page use:
Abstract: In this paper we obtain tight bounds on the space-complexity of computing the ergodic measure of a low-dimensional discrete-time dynamical system affected by Gaussian noise. If the scale of the noise is ε, and the function describing the evolution of the system is not itself a source of computational complexity, then the density function of the ergodic measure can be approximated within precision δ in space polynomial in log 1/ε + log log 1/δ. We also show that this bound is tight up to polynomial factors. In the course of showing the above, we prove a result of independent interest in space-bounded computation: namely, that it is possible to exponentiate an (n × n)-matrix to an exponentially large power in space polylogarithmic in n.
Publication Date: 2017
Citation: Braverman, Mark, Cristóbal Rojas, and Jon Schneider. "Tight space-noise tradeoffs in computing the ergodic measure." Sbornik: Mathematics 208, no. 12 (2017): pp. 1758-1783. doi:10.1070/SM8884
DOI: 10.1070/SM8884
ISSN: 1064-5616
EISSN: 1468-4802
Pages: 1758 - 1783
Type of Material: Journal Article
Journal/Proceeding Title: Sbornik: Mathematics
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.