Geodesic
Tight space-noise tradeoffs in computing the ergodic measure
Sbornik. Mathematics, Tome 208 (2017) no. 12, pp. 1758-1783 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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 $\varepsilon$, 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 $\delta$ in space polynomial in $\log 1/\varepsilon+\log\log 1/\delta$. 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\times n)$-matrix to an exponentially large power in space polylogarithmic in $n$. Bibliography: 25 titles.
Keywords: dynamical systems, space-bounded computations. 
@article{SM_2017_208_12_a2,
     author = {M. Braverman and C. Rojas and J. Schneider},
     title = {Tight space-noise tradeoffs in computing the ergodic measure},
     journal = {Sbornik. Mathematics},
     pages = {1758--1783},
     year = {2017},
     volume = {208},
     number = {12},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2017_208_12_a2/}
}
TY  - JOUR
AU  - M. Braverman
AU  - C. Rojas
AU  - J. Schneider
TI  - Tight space-noise tradeoffs in computing the ergodic measure
JO  - Sbornik. Mathematics
PY  - 2017
SP  - 1758
EP  - 1783
VL  - 208
IS  - 12
UR  - http://geodesic.mathdoc.fr/item/SM_2017_208_12_a2/
LA  - en
ID  - SM_2017_208_12_a2
ER  - 
%0 Journal Article
%A M. Braverman
%A C. Rojas
%A J. Schneider
%T Tight space-noise tradeoffs in computing the ergodic measure
%J Sbornik. Mathematics
%D 2017
%P 1758-1783
%V 208
%N 12
%U http://geodesic.mathdoc.fr/item/SM_2017_208_12_a2/
%G en
%F SM_2017_208_12_a2
M. Braverman; C. Rojas; J. Schneider. Tight space-noise tradeoffs in computing the ergodic measure. Sbornik. Mathematics, Tome 208 (2017) no. 12, pp. 1758-1783. http://geodesic.mathdoc.fr/item/SM_2017_208_12_a2/

[1] H. Alt, “Comparison of arithmetic functions with respect to boolean circuit depth (extended abstract)”, STOC' 84 Proceedings of the 16th annual ACM symposium on theory of computing (1984, Washington, DC), ACM, New York, 1984, 466–470 | DOI

[2] E. Asarin, O. Maler, A. Pnueli, “Reachability analysis of dynamical systems having piecewise-constant derivatives”, Theoret. Comput. Sci., 138:1 (1995), 35–65 | DOI | MR | Zbl

[3] Handbook of mathematical functions with formulas, graphs, and mathematical tables, National Bureau of Standards Applied Mathematics Series, 55, 3rd printing, with corrections, eds. M. Abramowitz, I. A. Stegun, Superintendent of Documents, U.S. Government Printing Office, Washington, D.C., 1965, xiv+1046 pp. | MR | MR | Zbl | Zbl

[4] I. Binder, M. Braverman, C. Rojas, M. Yampolsky, “Computability of the Brolin–Lyubich measure”, Comm. Math. Phys., 308:3 (2011), 743–771 | DOI | MR | Zbl

[5] G. Buntrock, C. Damm, U. Hertrampf, Ch. Meinel, “Structure and importance of logspace-MOD class”, Math. Systems Theory, 25:3 (1992), 223–237 | DOI | MR | Zbl

[6] M. Braverman, A. Grigo, C. Rojas, “Noise vs computational intractability in dynamics”, ITCS' 12 Proceedings of the 3rd Innovations in theoretical computer science conference (Cambridge, MA, 2012), ACM, New York, 2012, 128–141 | DOI | MR | Zbl

[7] M. Braverman, C. Rojas, J. Schneider, “Space-bounded church-turing thesis and computational tractability of closed systems”, Phys. Rev. Lett., 115:9 (2015), 098701 | DOI

[8] M. Braverman, M. Yampolsky, “Non-computable {J}ulia sets”, J. Amer. Math. Soc., 19:3 (2006), 551–578 | DOI | MR | Zbl

[9] M. Braverman, M. Yampolsky, “Constructing non-computable Julia sets”, STOC' 07 Proceedings of the 39th annual ACM symposium on theory of computing (San Diego, CA, 2007), ACM, New York, 2007, 709–716 | DOI | MR | Zbl

[10] A. Chiu, G. Davida, B. Litow, Integer division is in $NC^1$, 1995, 19 pp. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.3099&rep=rep1&type=pdf

[11] G. E. Collins, “Polynomial minimum root separation”, J. Symbolic Comput., 32:5 (2001), 467–473 | DOI | MR | Zbl

[12] T. M. Cover, J. A. Thomas, Elements of information theory, Wiley Ser. Telecom., John Wiley Sons, Inc., New York, 1991, xxiv+542 pp. | DOI | MR | Zbl

[13] G. Froyland, “Using Ulam's method to calculate entropy and other dynamical invariants”, Nonlinearity, 12:1 (1999), 79–101 | DOI | MR | Zbl

[14] S. Galatolo, M. Hoyrup, C. Rojas, “Dynamics and abstract computability: computing invariant measures”, Discrete Contin. Dyn. Syst., 29:1 (2011), 193–212 | DOI | MR | Zbl

[15] S. Galatolo, M. Monge, I. Nisoli, Existence of noise induced order, a computer aided proof, arXiv: 1702.07024

[16] S. Galatolo, I. Nisoli, “Rigorous computation of invariant measures and fractal dimension for maps with contracting fibers: 2D Lorenz-like maps”, Ergodic Theory Dynam. Systems, 36:6 (2016), 1865–1891 | DOI | MR | Zbl

[17] I. M. Gelfand, M. M. Kapranov, A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Math. Theory Appl., Birkhäuser Boston, Inc., Boston, MA, 1994, x+523 pp. | DOI | MR | Zbl

[18] J. Kari, V. Lukkarila, “Some undecidable dynamical properties for one-dimensional reversible cellular automata”, Algorithmic bioprocesses, Nat. Comput. Ser., Springer, Berlin, 2009, 639–660 | DOI | MR

[19] R. Mañé, Ergodic theory and differentiable dynamics, Ergeb. Math. Grenzgeb. (3), 8, Springer-Verlag, Berlin, 1987, xii+317 pp. | DOI | MR | Zbl

[20] C. Moore, “Unpredictability and undecidability in dynamical systems”, Phys. Rev. Lett., 64:20 (1990), 2354–2357 | DOI | MR | Zbl

[21] C. A. Neff, J. H. Reif, “An efficient algorithm for the complex roots problem”, J. Complexity, 12:2 (1996), 81–115 | DOI | MR | Zbl

[22] K. Petersen, Ergodic theory, Cambridge Stud. Adv. Math., 2, Cambridge Univ. Press, Cambridge, 1983, xii+329 pp. | DOI | MR | Zbl

[23] W. J. Savitch, “Relationships between nondeterministic and deterministic tape complexities”, J. Comput. System. Sci., 4:2 (1970), 177–192 | DOI | MR | Zbl

[24] P. Walters, An introduction to ergodic theory, Grad. Texts in Math., 79, Springer-Verlag, New York–Berlin, 1982, ix+250 pp. | MR | Zbl

[25] S. Wolfram, A new kind of science, Wolfram Media, Inc., Champaign, IL, 2002, xiv+1197 pp. | MR | Zbl