We formulate a new connection between instance compressibility (Harnik and Naor, 2010), 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 s 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))^{omega(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 {it 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.
展开▼
