Serendipity

I attended a talk this morning by Holger Hoos, from UBC, and then had a fascinating conversation with him over lunch. He’s on an 8 week driving tour across Canada and the US, stopping off at universities along the way to meet with colleagues give talks. Great idea – more academics should do this (although I can’t figure out what I’d do with the kids…)

Anyway, what piqued my interest was the framing Holger used for the talk: we live in interesting times, and are faced with many grand challenges: climate change, peak oil, complex diseases, market turmoil, etc. Many of these challenges are due to complexity of various kinds, and to tame this complexity we need to be able to understand, model and control complex systems. And of course, taming complexity is what much of computer science is about.

The core of his talk was a fascinating look at new heuristic algorithms for solving NP hard problems, e.g. algorithms that that outperform the best TSP algorithms and SAT solvers, by using machine learning techniques to tweak the parameters on the heuristics to optimize them for different kinds of input. Which leads to a whole new approach of empirical algorithm design and algorithm engineering. One theme throughout the talk was shift in focus for algorithm design from thinking about worst case analysis, to thinking about handling typical cases, which is something I’ve long felt is a problem with theoretical computer science, and one of the reasons the field has been largely irrelevant when tackling most real engineering problems.

Anyway, for all that I enjoyed the talk, there seemed  to be a gap between the framing (tackling the grand challenges of our time) and the technical content (solutions to computationally intractable problems). Over lunch we talked about this. My observation is that, for climate change in particular, I don’t believe there are any aspects of the challenge that require solving computationally complex problems. It would be nice if there were – it would help me complete my map of how the various subfields of computer science can contribute to tackling climate change. There are obvious applications for information systems (aka databases), graphics and visualization, human computer interaction (usable climate models!!), software engineering, ubiquitous computing (e.g. sensor networks), systems (e.g. power aware computing), and so on.

We talked a little about whether climate models themselves count, but here the main challenges are in optimizing continuous mathematics routines for high performance, rather than solving complex discrete mathematics problems. For example, we speculated whether some of Holger’s work on applying machine learning techniques to parameter tuning could be applied to the parameter schemes for climate models, but even here, I’m not convinced, because there is no oracle. The problem is that climate scientists can’t write down good correctness criteria for climate models because the problem isn’t to develop a “formally correct” model, but rather a scientifically useful one. The model is good if it helps test a scientific hypothesis about how (some aspect of) earth systems work. A model that gets a good fit with observational data because the parameters have been ‘over-tuned’ will get a poor reception in the climate science community; the challenge is to get a model that matches observational data because we’ve correctly understood the underlying physical processes, not because we’ve blindly twiddled the knobs. However, I might be being overly pessimistic about this, and there might be scope for some of these techniques because model tuning still remains a challenging task in climate modeling.

But the more urgent and challenging problems in climate change remain squarely in the realm of how to wean the world off its addiction to fossil fuels as rapidly as possible. This is a problem of information (and overcoming disinformation), of behaviour (individual and social), of economics (although most of modern economic theory is useless in this respect), and of politics. Computer Science has a lot to offer in tackling the information problems, and also some useful abstraction and modeling techniques to understand the other problems. And of course, software is a critical enabling technology in the switch to alternative energy sources. But I still don’t see any computational complexity problems that need solving in all of this. Tell me I’m wrong!