  Using geometric techniques like projection and dimensionality reduction, we
show that there exists a randomized sub-linear time algorithm that can estimate
the Hamming distance between two matrices. Consider two matrices ${\bf A}$ and
${\bf B}$ of size $n \times n$ whose dimensions are known to the algorithm but
the entries are not. The entries of the matrix are real numbers. The access to
any matrix is through an oracle that computes the projection of a row (or a
column) of the matrix on a vector in $\{0,1\}^n$. We call this query oracle to
be an {\sc Inner Product} oracle (shortened as {\sc IP}). We show that our
algorithm returns a $(1\pm \epsilon)$ approximation to ${{\bf D}}_{\bf M} ({\bf
A},{\bf B})$ with high probability by making ${\cal
O}\left(\frac{n}{\sqrt{{{\bf D}}_{\bf M} ({\bf A},{\bf
B})}}\mbox{poly}\left(\log n, \frac{1}{\epsilon}\right)\right)$ oracle queries,
where ${{\bf D}}_{\bf M} ({\bf A},{\bf B})$ denotes the Hamming distance (the
number of corresponding entries in which ${\bf A}$ and ${\bf B}$ differ)
between two matrices ${\bf A}$ and ${\bf B}$ of size $n \times n$. We also show
a matching lower bound on the number of such {\sc IP} queries needed. Though
our main result is on estimating ${{\bf D}}_{\bf M} ({\bf A},{\bf B})$ using
{\sc IP}, we also compare our results with other query models.
