Given three matrices $A, B,C \in \mathbb{Z}^{n \times n}$ we want to test whether $AB \neq C$. Assume that the arithmetic operations $+$ and $-$ take constant time when applied to numbers from $\mathbb{Z}$.
How can I state an algorithm with one-sided error that runs in $O(n^2)$ time and prove its correctness?
I tried it now for several hours but I can't get it right. I think I have to use the fact that for any $x \in \mathbb{Z}^n$ at most half of the vectors $s \in S = \left\{1, 0\right\}^n$ satisfy $x \cdot s = 0$, where $x \cdot s$ denotes the scalar product$\sum_{i=1}^{n} x_is_i$.