TR12-108 Authors: Arkadev Chattopadhyay, Rahul Santhanam

Publication: 5th September 2012 11:04

Downloads: 1888

Keywords:

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.