We formulate a new connection between instance compressibility \cite{Harnik-Naor10}), where the compressor uses circuits from a class $\C$, and correlation with
circuits in $\C$. We use this connection to prove the first lower bounds
on general probabilistic multi-round instance compression. We show that there
is no
probabilistic multi-round compression protocol for Parity in which the
computationally bounded party uses a non-uniform $\AC^0$-circuit and transmits
at most $n/(\log(n))^{\omega(1)}$ bits. This result is tight, and strengthens
results of
Dubrov and Ishai \cite{Dubrov-Ishai06}. We also show that a similar lower bound holds for Majority.

We also consider the question of {\it round separation}, i.e., whether
for each $r \geq 1$, there are functions which can be compressed better with
$r$ rounds of compression than with $r-1$ rounds. We answer this question
affirmatively for compression using constant-depth polynomial-size circuits.

Finally, we prove the first non-trivial lower bounds for 1-round compressibility of Parity by polynomial size $\mathrm{ACC}^0[p]$ circuits where $p$ is an odd prime.