We consider the problem of approximating the distance of two d-dimensional vectors x and y in the stream data model. In this model, the 2d coordinates are presented as a ``stream'' of data in some arbitrary order, where each data item includes the index and value of some coordinate and a bit that identifies the vector (x or y) to which it belongs. The goal is to minimize the amount of memory needed to approximate the distance. For the case of L^p-distance with p in [1,2], there are good approximation algorithms that run in polylogarithmic space in d (here we assume that each coordinate is an integer with O(log d) bits). However, it is still open whether such algorithms exist for any p>2. Here we prove that they do not exist for p>3. In particular, we prove an approximation-space tradeoff of approximating the maximum coordinate of the difference of two vectors. We show that for c>0, any randomized algorithm that approximates this maximum of two length d vectors within factor of d^c requires Omega(d^{1-6c}) space. As a consequence we show that for p>3/(1-6c), any randomized algorithm that approximates L^p distance of two length d vectors within a factor d^c requires Omega(d^{1-3/p-6c}) space.

The lower bound follows from a lower bound on the one-round communication complexity of this problem. This lower bound is proved using a combination information theory and fourier analysis.

This is joint work with Michael Saks.