We formulate a new connection between instance compressibility \cite{Harnik-Naor10}), where the compressor uses circuits from a class \C, and correlation withcircuits in \C. We use this connection to prove the first lower boundson general probabilistic multi-round instance compression. We show that there is noprobabilistic multi-round compression protocol for Parity in which the computationally bounded party uses a non-uniform \AC0-circuit and transmitsat most n(log(n))(1) bits. This result is tight, and strengthens results ofDubrov 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., whetherfor each r1, there are functions which can be compressed better withr rounds of compression than with r−1 rounds. We answer this questionaffirmatively 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 ACC0[p] circuits where p is an odd prime