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

# Author: Alex Andoni

# STOC/SoCG workshop day & ITCS graduating bits

A couple announcements on happenings in Cambridge: STOC/SoCG joint workshop day: this year, STOC and SoCG are co-located in Cambridge, MA, and will hold a joint workshop day on June 18th, 2016. The goal of this day is to have events of common interest to both communities and thus foster further collaboration. The schedule already includes plenary … Continue reading STOC/SoCG workshop day & ITCS graduating bits

# 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!

# Lists of Open Problems

Open problems are of course very valuable for setting research directions and pointing out current or grand challenges. I would like to point out two more recent lists of open problems that are "closer to home" for me at least.sublinear.info is a wikified List of Open Problems in Sublinear Algorithms. This one is actually a few … Continue reading Lists of Open Problems

# 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

# Higher Lower Bounds: Just Ask for More!

In memory of Mihai Pătraşcu. Continuing the spirit of the previous post, in this post I will describe a specific technique for proving lower bounds for (static) data structures, when the space is (near) linear. This technique was introduced in the paper by Mihai and Mikkel Thorup, called "HIGHER lower Bounds for Near-Neighbor and F … Continue reading Higher Lower Bounds: Just Ask for More!

# 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)