  The exact computation of the number of distinct elements (frequency moment
$F_0$) is a fundamental problem in the study of data streaming algorithms. We
denote the length of the stream by $n$ where each symbol is drawn from a
universe of size $m$. While it is well known that the moments $F_0,F_1,F_2$ can
be approximated by efficient streaming algorithms, it is easy to see that exact
computation of $F_0,F_2$ requires space $\Omega(m)$. In previous work, Cormode
et al. therefore considered a model where the data stream is also processed by
a powerful helper, who provides an interactive proof of the result. They gave
such protocols with a polylogarithmic number of rounds of communication between
helper and verifier for all functions in NC. This number of rounds
$\left(O(\log^2 m) \;\text{in the case of} \;F_0 \right)$ can quickly make such
protocols impractical.
  Cormode et al. also gave a protocol with $\log m +1$ rounds for the exact
computation of $F_0$ where the space complexity is $O\left(\log m \log n+\log^2
m\right)$ but the total communication $O\left(\sqrt{n}\log m\left(\log n+ \log
m \right)\right)$. They managed to give $\log m$ round protocols with
$\operatorname{polylog}(m,n)$ complexity for many other interesting problems
including $F_2$, Inner product, and Range-sum, but computing $F_0$ exactly with
polylogarithmic space and communication and $O(\log m)$ rounds remained open.
  In this work, we give a streaming interactive protocol with $\log m$ rounds
for exact computation of $F_0$ using $O\left(\log m \left(\,\log n + \log m
\log\log m\,\right)\right)$ bits of space and the communication is $O\left(
\log m \left(\,\log n +\log^3 m (\log\log m)^2 \,\right)\right)$. The update
time of the verifier per symbol received is $O(\log^2 m)$.
