This post has some tidbits regarding the problem of computing a 'fingerprint' of a long sequence of characters, often called 'string hashing'. Most of the results I will describe are quite old, but they are scattered upon several papers, so I think it is worthwhile to have a post where they are  put together. This … Continue reading How to collapse the universe?

As promised in the previous post, I will explain how an algorithm designed for the approximate near neighbor problem, the LSH algorithm, leads to a solution for the exact near neighbor problem (henceforth NNS). While, the algorithm for the exact problem will not have full guarantees, we will be able to give some partial guarantees. Usually … Continue reading Exact Algorithms from Approximation Algorithms? (part 2)

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. … Continue reading Exact Algorithms from Approximation Algorithms? (part 1)

Tiny ToCT studies the following question: could a marvelous field of huge impact be squeezed into a tiny space of 140 characters? Good luck!

By Ittai Abraham and Moshe Babaioff Can we use Economic insights to better understand the ecosystem of Academic Publication? In light of recent changes, how can we optimize this ecosystem? After all, this is a system with many participants with different interests: authors, publishers, academic institutions, consumers (of academic publications) which can all be modeled … Continue reading An Economic Perspective on Academic Publication