(Graham Cormode reports from Day 2 of the fourth Bristol Algorithms Days)

Day 2, and I seem to be lacking energy: maybe it’s the lack of adrenaline from giving a talk, the jet lag kicking in, or the after effects of the workshop banquet the night before (the first dinner I have had at a swimming pool). But energy is the order of the day: two talks on energy efficiency. With political emphasis on sustainability and energy efficiency, expect to see more work using these keywords. Prudence Wong of Liverpool, and Lap-Kei Lee at MPI talked about related works on processor scheduling: now processors can go faster or slower (or sleep), with different energy costs. Since the tradeoff is non-linear (it’s more like cubic), scheduling problems get revisited with the added goal of minimizing energy costs while time objectives are met. This seems to have inspired the scheduling community, and while techniques look familiar (choosing the potential function, obtaining competitive ratios) the results are new.

The question I am left with is how should the rest of theory contribute to research on energy efficiency (which they surely will, given funding for this topic)? In the sublinear world, we could take the lazy route and claim “because our algorithms are fast and use small memory, they are more efficient than running the exact algorithm”. But this does not lead us to new challenges. Maybe we need a different way of counting the energy cost of an algorithm, which we can evaluate in big-Oh notation along with the time and space bounds.

The current buzzphrase in UK funding is “economic impact”: work is now evaluated in terms of its broader impact on the economy. Naturally, this change to the status quo has caused some consternation, especially to the more theoretically minded. “How can we put a price on fundamental research?” the question goes. But it is not such a bad exercise to ask what impact (if any) our work could have on the world. Again, a lazy route is to pontificate on past glories of theory in general, but I’d to see people form more coherent arguments about how their work has had impact. I’m reminded of Muthu’s comments about billion dollar problems and trillion dollar problems. It is easy to claim to work in areas that contribution $$$s to the economy: but does your work have a non-zero (and non-negative) contribution to this sum?

The last session has talks from two stringmasters from Bar-Ilan who need no surnames (Ami and Moshe), and a combinatorial tour-de-force from Alex Tiskin. Nothing streaming here, so I refrain from summarizing to save my energies…

Thanks go to Raphael Clifford and Malcolm MacCallum for organizing, along with a large band of helpers. Algorithms (whether streamy, stringy, energetic or otherwise) are active in the UK, and are surely having some economic impact.

(end of Graham’s post)

BONUS! Some toponymy… So why is Bristol, called Bristol? Well, according to the web, the name comes from “Brycgstow” which means something like “the meeting place by the bridge” in Anglo-Saxon. Fascinating, I hear you say.
Well, more intriguingly, if you believe this BBC story then it could have been named by the Ossetians (in the guise of the Sarmatians or the Alans) along with London (“standing water”), Belfast (“broken spade”), Crewe, Hove, and a bunch of other places in the UK. Yes, we’re talking about the Ossetia that’s 2255 miles from Bristol. But should I believe everything the BBC tells me?