SGER: Multidisciplinary Aspects of Computation Theory

This project will explore a multidisciplinary collection of related problems in

which the theory of computing plays a fundamental role. The problems involve

a variety of topics in computational complexity, algorithmic information theory,

stochastic processes, statistical inference, arti.cial intelligence, fractal geometry,

dynamical systems, game theory, and other areas, but they have several crucial

commonalities: The problems are ones that involve computability and/or complexity theory

in fundamental conceptual respects. The problems are stochastic in the sense that they or their solutions involve some sort of randomness. The problems are dynamic in the sense that they or their solutions involve analyticor topological methods in addition to the discrete and algebraic methods that more typically arise in the theory of computing. The problems are strategic in the sense that they or their solutions involve the design and analysis of algorithmic strategies for betting, prediction, learning, game-playing, or some other task that is carried out in an environment

containing adversity.