Before revision:  This is within a polylogarithmic factor of the best-known guarantee for equi-joins and even  \mathcal{O}(n+k), the time it takes to look at the input and output k answers .
After revision:  This is within a polylogarithmic factor of the best known complexity for equi-joins and even \mathcal{O}(n+k), the time it takes to look at the input and output k answers .