Taming the Complexity Monster

Abstract:

We live in interesting times - as individuals, as members of various
communities and organisations, and as inhabitants of planet Earth, we
face many challenges, ranging from climate change to resource
limitations, from market risks and uncertainties to complex
diseases. To some extent, these challenges arise from the complexity
of the systems we are dealing with and of the problems that arise from
understanding, modelling and controlling these systems. As computing
scientists and IT professionals, we have a lot to contribute: solving
complex problems by means of computer systems, software and algorithms
is an important part of what our field is about.

In this talk, I will focus on one particular type of complexity that
has been of central interest in many areas 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.)