Bristol Algorithms Days

A quick note of thanks to the organisers of Bristol Algorithms Days, a 2-day workshop (just ended) featuring talks on ongoing work on algorithms and proof techniques for analysing their properties. The event attracted quite a few colleagues from the UK and a surprising number of visitors from further afield. I got a useful introduction to some important lines of research that I’d been vaguely aware of, ones that deserve to be somewhat familiar to those of us in the algorithms community. A notable one is SETH-hardness, and 3SUM-hardness, and their usefulness for providing evidence that various polynomial-time algorithms cannot be improved on (e.g. the quadratic time taken by dynamic programming for problems like longest common subsequence, and computation of Frechet distance as well as other geometrical problems) (talk by Karl Bringmann). Another topic (talk by Iordanis Kerenidis): quantum algorithms that give exponential speedup for certain linear operations, and the applicability of these to machine learning; apparently there’s interest at Google and Microsoft in the potential applicability of such algorithms to their data. A talk by Alina Ene on computational learning problems that can be modelled as constrained submodular maximisation problems was interesting to me, having gotten somewhat familiar with submodular functions in economic-theory contexts. That list is non-exhaustive…