Holger H. Hoos is an Associate Professor at the Computer Science Department of the University of British Columbia (Canada), where he is a co-founder of the Bioinformatics, Empirical and Theoretical Algorithmics (BETA) Laboratory and a member of the Laboratory for Computational Intelligence (LCI); he is also a faculty associate of the Peter Wall Institute for Advanced Studies at UBC. Holger's main research areas span empirical algorithmics, artificial intelligence, bioinformatics and computer music. Holger's 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 book chapters, journals, and at major conferences in artificial intelligence, operations research, molecular biology and computer music.
(For further information, see Holger's web page at http://www.cs.ubc.ca/~hoos)

AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS   Info

AG Audience

English

45 Minutes

Saarbrücken

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 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, and I will 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, the analysis of financial market data and the prediction and design of biomolecular (RNA and protein) structures.

Frank Neumann

--email hidden

passcode not visible

logged in users only