Alex Andoni starts with a reflection of how the theory community has evolved to tackle problems by approximate algorithms, but also algorithms that performs good given some constraints on the structured of the problem. This post is a nice overview of Locality-Sensitive Hashing and an introduction to how we could solve exact near neighbor search using approximate randomized algorithm as LSH too.
One great “soft” challenge in (T)CS I find to be how to go on to find useful algorithms for problems that we believe (or have even proven!) to be hard in general. Let me explain by giving the all-too-common-example:
Practitioner: I need to solve problem X.
Theoretician: Nice question, let me think… Hm, it seems hard. I can even prove that, under certain assumptions, we cannot do anything non-trivial.
Practitioner: Slick… But I still need to solve it. Can you do anything?
Theoretician: If I think more, I can design an algorithm that gives a solution up to factor 2 within the actual solution!
Practitioner: Interesting, but that’s too much error nonetheless… How about 1.05?
Theoretician: Nope, essentially as hard as exact solution.
Practitioner: Thanks. But I still need to deliver the code in a month. I guess I will go and hack something by myself — anyways my instances are…
View original post 536 more words
Eliezer Silva 