I am a Professor at the Santa Fe Institute. I work at the interface of physics, computer science, and mathematics, such as phase transitions in statistical inference: when data becomes too incomplete or too noisy, it can suddenly become impossible to find underlying patterns in it, or tell if a pattern is really there. This includes finding clusters in high-dimensional data and finding communities in social or biological networks. How can we locate these phase transitions? And how can we design optimal algorithms that succeed all the way up to this point?
I have also worked on phase transitions in search and optimization problems, where problems suddenly become unsolvable when they become too constrained; quantum computation and quantum algorithms for the Graph Isomorphism problem; the computational complexity of predicting physical systems, and of solving systems of equations; percolation, topological defects, and Monte Carlo algorithms; games, tilings, and cellular automata; the stability of financial markets, epidemics in networks, and universality in human language; and braided orbits in the 3-body problem.
Papers to be discussed