All reports by Author Arkadev Chattopadhyay:

__
TR12-108
| 4th September 2012
__

Arkadev Chattopadhyay, Rahul Santhanam#### Lower Bounds on Interactive Compressibility by Constant-Depth Circuits

__
TR11-048
| 10th April 2011
__

Arkadev Chattopadhyay, Shachar Lovett#### Linear systems over abelian groups

Arkadev Chattopadhyay, Rahul Santhanam

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 ...
more >>>

Arkadev Chattopadhyay, Shachar Lovett

We consider a system of linear constraints over any finite Abelian group $G$ of the following form: $\ell_i(x_1,\ldots,x_n) \equiv \ell_{i,1}x_1+\cdots+\ell_{i,n}x_n \in A_i$ for $i=1,\ldots,t$ and each $A_i \subset G$, $\ell_{i,j}$ is an element of $G$ and $x_i$'s are Boolean variables. Our main result shows that the subset of the Boolean ... more >>>