PACM Colloquium: Bernard Chazelle, Princeton University

Graphs, Dynamics, and Renormalization

Nonlinear Markov chains are probabilistic models commonly used in physics, biology, and the social sciences. In "Markov influence systems," the transition probabilities of the chains may change as a function of the current state distribution. This talk will discuss a renormalization framework to help us analyze these systems. It allows us to show, for example,that Markov influence systems of the irreducible kind are almost surely periodic. I will place this work in the broader context of a research program whose main objective is to build new mathematical tools for "natural algorithms" and, more generally, out-of-equilibrium dynamics.

Bernard Chazelle is Eugene Higgins Professor of Computer Science at Princeton University, where he has been on the faculty since 1986. His current research focuses on the “algorithmic nature” of living systems. A professor at the Collège de France in Paris in recent years as well as a member of the Institute for Advanced Study in Princeton, he received his PhD in computer science from Yale University in 1980. The author of the book, "The Discrepancy Method," he is a fellow of the American Academy of Arts and Sciences, the European Academy of Sciences, the Association for Computing Machinery, and the recipients of three Best-Paper awards from SIAM.