""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).""

"Oliver Friedman, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form for ... two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding if this is possible was an open problem for several decades." And they do it using MDPs!

The Herbert Simon collection at the CMU library

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."

"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."

FOCS 2008 tutorials (Terry Tao on randomness in combinatorics; Dan Boneh on crypto; Dan Spielman on graph spectra)

Lecture notes by Ryan O'Donnell (CMU)