Lower Bounds on Interactive Compressibility by Constant-Depth Circuits

We formulate a new connection between instance compressibility [1]), 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 AC0-circuit and transmits at most n/(log(n))ω(1) bits. This result is tight, and strengthens results of Dubrov and Ishai. We also show that a similar lower bound holds for Majority. We also consider the question of round separation, i.e., whether for each r ≥ 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 ACC0[p] circuits where p is an odd prime.