Expertise

• Combinatorial Optimization
• Discrete Algorithms
• Statistical Physics
• Analysis of Complex Networks

Research

My research has combined statistical physics, discrete mathematics and computer science, focusing primarily on local search algorithms in combinatorial optimization. Much of my work has involved using insights from physical phenomena to motivate improved optimization methods. My collaborator Stefan Boettcher and I developed Extremal Optimization, a powerful general-purpose method based on self-organized criticality that finds approximate solutions to NP-hard optimization problems.

I have also been very interested in the role that phase transitions can play in helping us analyze and solve computationally hard problems over random ensembles of instances. This was the subject of a 2006 Oxford University Press volume, "Computational Complexity and Statistical Physics", that I edited together with Gabriel Istrate and Cris Moore.

Some of my recent research directions have been motivated by the scientific challenges of rapidly processing and extracting information. One of the most crucial needs is for distributed algorithms that in practice provide good linear-time performance. Recent examples are message-passing algorithms, such as survey propagation, that have been developed by a collaboration of computer scientists and statistical physicists and have proven successful in applications from constraint satisfaction to coding theory.

From 2003 to 2006, I was Associate Director of the NSF-funded Institute for Pure and Applied Mathematics at UCLA. During this period we made a significant effort to address upcoming large-scale data challenges and to train a new generation of researchers in the necessary techniques. For a good example, see the 2005 Graduate Summer School on Intelligent Extraction of Information from Graphs and High-Dimensional Data jointly sponsored by LANL.

Publications

For publications see Allon Percus' web page