Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-108 | 4th September 2012 16:14

Lower Bounds on Interactive Compressibility by Constant-Depth Circuits


Authors: Arkadev Chattopadhyay, Rahul Santhanam
Publication: 5th September 2012 11:04
Downloads: 3230


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.

ISSN 1433-8092 | Imprint