In this talk, I will focus on one particular type of complexity that has been of central interest in many areads within computing science and its applications, namely computational complexity, and in particular, NP-hardness. I will investigate the question to which extent NP-hard problems are as formidable as is often thought, and I will present an overview of research that fearlessly, and perhaps sometimes foolishly, attempts to deal with these problems in a rather pragmatic way. I will also argue that the area of empirical algorithmics holds the key to solving computationally challenging problems more effectively than many would think possible, while at the same time producing interesting scientific insights. The problems I will be covering include SAT and TSP, two classical and very prominent NP-hard problems; in particular, I will present empirical scaling results for the best-performing complete TSP solver currently known and discuss recent improvements in the state of the art in solving SAT-encoded software verification problems. I will also briefly discuss new results in the areas of timetabling, protein structure prediction and analysis of financial market data.
Bio: Holger H. Hoos is an Associate Professor at the Computer Science Department of the University of British Columbia (Canada). His main research areas span empirical algorithmics, artificial intelligence, bioinformatics and computer music. He is a co-author of the book "Stochastic Local Search: Foundations and Applications", and his research has been published in numerous book chapters, journals, and at major conferences in artificial intelligence, operations research, molecular biology and computer music. Holger is a Faculty Associate of the Peter Wall Institute for Advanced Studies and currently serves as President of the Canadian Artificial Intelligence Association (CAIAC). (For further information, see Holger's web page at http://www.cs.ubc.ca/~hoos.)
Refreshments will be provided at 10:45