""We survey an area of recent development, relating dynamics to theoretical computer science. We discuss the theoretical limits of simulation and computation of interesting quantities in dynamical systems. We will focus on central objects of the theory of dynamics, as invariant measures and invariant sets, showing that even if they can be computed with arbitrary precision in many interesting cases, there exists some cases in which they can not. We also explain how it is possible to compute the speed of convergence of ergodic averages (when the system is known exactly) and how this entails the computation of arbitrarily good approximations of points of the space having typical statistical behaviour (a sort of constructive version of the pointwise ergodic theorem).""

"Observer Mechanics is an inquiry into the subject of perception. It suggests an approach to the study of perception that attempts to be both rigorous and general. A central thesis of Observer Mechanics is that every perceptual capacity (e.g., stereovision, auditory localization, sentence parsing, haptic recognition, and so on) can be described as an instance of a single formal structure: viz., an "observer.""

John Baez blogs about his paper with Mike Stay on algorithmic thermodynamics

"We adapt tools from information theory to analyze how an observer comes to synchronize with the hidden states of a finitary, stationary stochastic process. We show that synchronization is determined by both the process's internal organization and by an observer's model of it. We analyze these components using the convergence of state-block and block-state entropies, comparing them to the previously known convergence properties of the Shannon block entropy. Along the way, we introduce a hierarchy of information quantifiers as derivatives and integrals of these entropies, which parallels a similar hierarchy introduced for block entropy. We also draw out the duality between synchronization properties and a process's controllability. The tools lead to a new classification of a process's alternative representations in terms of minimality, synchronizability, and unifilarity."

The Herbert Simon collection at the CMU library

"...we present a simple modification of the BP algorithm which gives a fully polynomial-time randomized approximation scheme (FPRAS)...This is the first instance where BP is proved to have fully-polynomial running time."

A course taught by Christos Papadimitriou

Issue on Interface of Probability and Algorithms

ICSI tech repots

Steven M. LaValle

Terry Tao explains the recent paper by Robin Moser.

"This paper seeks to explode the myth that Turing Machines (TM) are the universal model for all computation."

Leonid (Aryeh) Kontorovich

"The main point is this: an information theory bound yields an upper bound on the running time of a computational process."

"Let me show by analogy why limiting research to computational questions is bad for any field. Except in computer science, computational aspects play little role in the development of fundamental theories: Consider e.g. set theory with axiom of choice, foundations of logic, exact/full minimax for zero-sum games, quantum (field) theory, string theory, … Indeed, at least in physics, every new fundamental theory seems to be less computable than previous ones."

Workshop on the Frontiers in Distributed Communication, Sensing and Control, October 31 - November 2, 2008, Yale University

Lecture notes by Ryan O'Donnell (CMU)