  Motivated by recommendation systems, we consider the problem of estimating
block constant binary matrices (of size $m \times n$) from sparse and noisy
observations. The observations are obtained from the underlying block constant
matrix after unknown row and column permutations, erasures, and errors. We
derive upper and lower bounds on the achievable probability of error. For fixed
erasure and error probability, we show that there exists a constant $C_1$ such
that if the cluster sizes are less than $C_1 \ln(mn)$, then for any algorithm
the probability of error approaches one as $m, n \tends \infty$. On the other
hand, we show that a simple polynomial time algorithm gives probability of
error diminishing to zero provided the cluster sizes are greater than $C_2
\ln(mn)$ for a suitable constant $C_2$.
