A Near-Optimal Algorithm for L1-Difference

Understand

We give the first L_1-sketching algorithm for integer vectors which produces nearly optimal sized sketches in nearly linear time.

• This answers the first open problem in the list of open problems from the 2006 IITK Workshop on Algorithms for Data Streams.
• Specifically, suppose Alice receives a vector x in {-M,...,M}^n and Bob receives y in {-M,...,M}^n, and the two parties share randomness.
• Each party must output a short sketch of their vector such that a third party can later quickly recover a (1 +/- eps)-approximation to ||x-y||_1 with 2/3 probability given only the sketches.