INTERDISCIPLINARY STOCHASTIC PROCESSES COLLOQUIUM Tuesday October 19, room 60 Evans, 4.10 - 5.00pm Speaker: Alistair Sinclair, UC Berkeley Title: Phase Transitions and Mixing Times Abstract: Recent work on random satisfiability and other problems has raised the possibility of deep connections between phase transitions (as studied in physics) and computational complexity. Markov chain Monte Carlo algorithms provide one of the most compelling examples to date of this connection. In many cases, a phase transition in a physical system is reflected in a dramatic jump in the running time of a naturally associated Monte Carlo algorithm. In this talk I will illustrate various aspects of the above phenomenon, with special emphasis on the classical Ising model. No knowledge of statistical physics will be assumed. This is joint work with (in various combinations) Martin Dyer, Fabio Martinelli, Eric Vigoda and Dror Weitz.