A better lower bound when $p=1$ is $n \log n - n (\log \log n + 3/2)$ bits, where $\log = \log_2$. (The $3/2$ term can be made arbitrarily close to $1$ for large enough $n$, and asymptotically it is $\log\log e - \log e \approx 0.91$.)

One can also apply a straightforward reduction from a graph connectivity communication game to obtain a less explicit $\Omega(n \log n)$ lower bound. However, since the implicit constant factor relates to the number of blocks guaranteed by Szemerédi's Regularity Lemma, it seems to end up so small as to be useless for applications.

So a more precise lower bound for the $p$-pass case is $\frac{1}{p}(n\log n - n(\log\log n + 3/2))$. I remain unconvinced that this is the true lower bound, since achieving such a bound seems unlikely -- the true dependence on $p$ seems to be weaker than an inverse proportion. However, the bound should be at least $\Omega(\frac{1}{p}n\log n)$, improving $\Omega(n/p)$.

A better lower bound when $p=1$ is $n \log n - n (\log \log n + 3/2)$ bits, where $\log = \log_2$. (The $3/2$ term can be made arbitrarily close to $1$ for large enough $n$, and asymptotically it is $\log\log e - \log e \approx 0.91$.)

One can also apply a straightforward reduction from a graph connectivity communication game to obtain a less explicit $\Omega(n \log n)$ lower bound. However, since the implicit constant factor relates to the number of blocks guaranteed by Szemerédi's Regularity Lemma, it seems to end up so small as to be useless for applications.

So a more precise lower bound for the $p$-pass case is $\frac{1}{p}(n\log n - n(\log\log n + 3/2))$. I remain unconvinced that this is the true lower bound, since achieving such a bound seems unlikely -- the true dependence on $p$ seems to be weaker than an inverse proportion. However, the bound should be at least $\Omega(\frac{1}{p}n\log n)$, improving $\Omega(n/p)$.

A better lower bound when $p=1$ is $n \log n - n (\log \log n + 3/2)$ bits, where $\log = \log_2$. (The $3/2$ term can be made arbitrarily close to $1$ for large enough $n$, and asymptotically it is $\log\log e - \log e \approx 0.91$.)

One can also apply a straightforward reduction from a graph connectivity communication game to obtain a less explicit $\Omega(n \log n)$ lower bound. However, since the implicit constant factor relates to the number of blocks guaranteed by Szemerédi's Regularity Lemma, it seems to end up so small as to be useless for applications.

So a more precise lower bound for the $p$-pass case is $\frac{1}{p}(n\log n - n(\log\log n + 3/2))$. I remain unconvinced that this is the true lower bound, since achieving such a bound seems unlikely -- the true dependence on $p$ seems to be weaker than an inverse proportion. However, the bound should be at least $\Omega(\frac{1}{p}n\log n)$, improving $\Omega(n/p)$.

A better lower bound when $p=1$ is $n \log n - n (\log \log n + 3/2)$ bits, where $\log = \log_2$. (The $3/2$ term can be made arbitrarily close to $1$ for large enough $n$, and asymptotically it is $\log\log e - \log e \approx 0.91$.)

One can also apply a straightforward reduction from a graph connectivity communication game to obtain a less explicit $\Omega(n \log n)$ lower bound. However, since the implicit constant factor relates to the number of blocks guaranteed by Szemerédi's Regularity Lemma, it seems to end up so small as to be useless for applications.

So a more precise lower bound for the $p$-pass case is $\frac{1}{p}(n\log n - n(\log\log n + 3/2))$. I remain unconvinced that this is the true lower bound, since achieving such a bound seems unlikely -- the true dependence on $p$ seems to be weaker than an inverse proportion. However, the bound should be at least $\Omega(\frac{1}{p}n\log n)$, improving $\Omega(n/p)$.