One algorithm to rule them all: One join query at a time

We present a recent algorithm (PODS 2012) that is the first provably optimal (worst-case) algorithm to compute database joins.

As a special case, we show that this join algorithm implies (i) The first algorithmic versions of some well-known geometric inequalities due to Loomis and Whitney (and their generalizations by Bollobas and Thomason); (ii) Algorithmically list recoverable codes that work with parameters that no known algorithmic list recovery result work with (e.g. those based on the Reed-Solomon codes) and an application of this result in designing sublinear time decodable compressed sensing schemes; (iii) Worst-case optimal algorithm to list all occurrences of any fixed hypergraph H in a given large hypergraph G.

We believe that this algorithm should find many more applications. (If time permits, I'll also mention some followup work on instance optimal join algorithms.)

This talk will focus on (i) and (ii) and is based on joint works with Gilbert, Ngo, Nguyen, Porat, Re and Strauss.