Understanding Complexity: Recent Developments and Directions

Professor Bart Selman, Cornell University, Computer Science Department

Recently, we have made considerable progress towards a better understanding of the nature of hard computational problems. In particular, by exploiting connections between combinatorial search problems and models from statistical physics, we now have methods that enable a much finer-grained characterization of computational complexity than the standard worst-case complexity measures. These findings provide insights into new algorithmic strategies based on randomization and distributed algorithm portfolios. I will survey the recent progress in this area and I will discuss implications for the design of more robust computational systems.

---

BIOGRAPHY

Bart Selman is an Associate Professor of Computer Science at Cornell University. He previously was a principal scientist at AT&T Bell Laboratories. He holds a Ph.D. and M.Sc. in computer science from the University of Toronto, and a M.Sc. in physics from Delft University of Technology. His research has covered many areas in artificial intelligence and computer science, including tractable inference, knowledge representation, natural language understanding, stochastic search methods, theory approximation, knowledge compilation, planning, default reasoning, and the connections between computer science and physics (phase transition phenomena). He has received four best paper awards at the American and Canadian national artificial intelligence conferences, and at the International Conference on Knowledge Representation. He holds an NSF CAREER Award and is an Alfred P. Sloan Research Fellow.

For more info, see www.cs.cornell.edu/home/selman.