ECCC-Report TR12-108https://eccc.weizmann.ac.il/report/2012/108Comments and Revisions published for TR12-108en-usWed, 05 Sep 2012 11:04:06 +0300
Paper TR12-108
| Lower Bounds on Interactive Compressibility by Constant-Depth Circuits |
Rahul Santhanam,
Arkadev Chattopadhyay
https://eccc.weizmann.ac.il/report/2012/108
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.Wed, 05 Sep 2012 11:04:06 +0300https://eccc.weizmann.ac.il/report/2012/108