Speaker: Holger H. Hoos
The University of British Columbia,
Vancouver
Title: 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.)