Tight lower bounds for the distinct elements problem

We prove strong lower bounds for the space complexity of (ε, δ)-approximating the number of distinct elements F₀ in a data stream. Let m be the size of the universe from which the stream elements are drawn. We show that any one-pass streaming algorithm for (ε, δ)-approximating F₀ must use Ω(1/ε²) space when ε = Ω(m^-1(9 + k)/), for any k > 0, improving upon the known lower bound of Ω(1/ε) for this range of ε. This lower bound is tight up to a factor of log log m for small ε and log 1/ε for large ε. Our lower bound is derived from a reduction from the one-way communication complexity of approximating a Boolean function in Euclidean space. The reduction makes use of a low-distortion embedding from an l₂ to l₁ norm.