Speaker:  Bart Selman
Affiliation: Cornell University, Department of Computer Science
Date:  1/27/00
Time & Location:  4:15PM, 101 Phillips
Title: Understanding Complexity: Recent Developments and Directions

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.