Call for proposals for FOCS’16 workshop/tutorial (half-)day

Following the proud tradition of previous STOC/FOCS conferences, FOCS'16 will also have a (half) day of workshop/tutorials on Saturday, October 8th, right before the conference starts. You are invited to submit your proposal of workshop or tutorial by August 31st; see details here. In short: you just need to propose an exciting theme and arrange the speakers. We will … Continue reading Call for proposals for FOCS’16 workshop/tutorial (half-)day

Congrats to ACM awards winners!

ACM has just announced its awards. In particular, the Paris Kanellakis Theory and Practice award was given to Andrei Broder, Moses Charikar, and Piotr Indyk, for their work on Locality-Sensitive Hashing (LSH)! LSH has already been featured in our blog, and will likely be again 🙂 The citation says: "For their groundbreaking work on Locality-Sensitive Hashing that has had … Continue reading Congrats to ACM awards winners!

High frequency moments via max-stability

In this post, I will present what I think is a simple(r) algorithm for estimating the $latex k>2$ frequency moment, or simply the $latex \ell_k$ norm of a vector, in the sketching/streaming model. In fact, the algorithm is just a weak embedding of $latex n$-dimensional $latex \ell_k$ into $latex \ell_\infty$ of dimension $latex m=O(n^{1-2/k}\log n)$ … Continue reading High frequency moments via max-stability

Exact Algorithms from Approximation Algorithms? (part 2)

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)

Exact Algorithms from Approximation Algorithms? (part 1)

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)