18
$\begingroup$

In 1979, Freivalds showed that verifying matrix products over any field can be done in randomized $O(n^2)$ time. More formally, given three matrices A, B, and C, with entries from a field F, the problem of checking whether AB = C has a randomized $O(n^2)$ time algorithm.

This is interesting because the fastest known algorithm for multiplying matrices is slower than this, so checking if AB = C is faster than computing C.

I want to know what is the most general algebraic structure over which matrix product verification still has an $O(n^2)$ time (randomized) algorithm. Since the original algorithm works over all fields, I guess it works over all integral domains too.

The best answer I could find to this question was in Subcubic Equivalences Between Path, Matrix, and Triangle Problems, where they say "matrix product verification over rings can be done in $O(n^2)$ randomized time [BK95]." ([BK95]: M. Blum and S. Kannan. Designing programs that check their work. J. ACM, 42(1):269–291, 1995.)

First, are rings the most general structure on which this problem has an $O(n^2)$ randomized algorithm? Second, I couldn't see how the results of [BK95] show an $O(n^2)$ time algorithm over all rings. Can someone explain how that works?

$\endgroup$
  • $\begingroup$ A stupid question: is it obvious that deterministic verification is as hard as multiplication? What if you are given not only A, B, and C but also a compact certificate; does it help anything? $\endgroup$ – Jukka Suomela Apr 7 '11 at 21:16
  • $\begingroup$ @Jukka: I believe the best deterministic algorithm for this problem is no faster than matrix multiplication, but I don't know if there is a reason why this should be the case. About the second question, if AB is not equal to C, then there is a short certificate that works: the entry of C that is incorrect, and the corresponding row of A and column of B. $\endgroup$ – Robin Kothari Apr 8 '11 at 5:17
14
$\begingroup$

Here's a quick argument for why it works over rings. Given matrices $A$, $B$, $C$, we verify $A B = C$ by picking a random bit vector $v$, then checking if $ABv = Cv$. This clearly passes if $AB = C$.

Suppose $AB \neq C$ and $ABv = Cv$. Let $D = AB - C$. $D$ is a nonzero matrix for which $Dv = 0$. What's the probability that this occurs? Let $D[i',j']$ be a nonzero entry. By assumption, $\sum_{j} D[i',j] v[j] = 0$. With probability $1/2$, $v[j'] = 1$, so we have

$D[i',j'] + \sum_{j\neq j'} D[i',j] v[j] = 0$.

Any ring under its addition operation is an additive group, so there is a unique inverse of $D[i',j']$, i.e., $-D[i',j']$. Now, the probability of the bad event $-D[i',j'] = \sum_{j\neq j'} D[i',j] v[j]$ is at most $1/2$. (One way to see this is the "principle of deferred decisions": in order for the sum to equal $-D[i',j']$, at least one other $D[i',j]$ must be nonzero. So consider the $v[j]$'s corresponding to these other nonzero entries. Even if we set all of these $v[j]$'s except for one of them optimally, there is still equal probability for the last one being $0$ or $1$, but still only one of these values could make the final sum equal to $-D[i',j']$.) So with probability at least $1/4$, we successfully find that $Dv \neq 0$, when $D$ is nonzero. (Note $v[j]$ and $v[j']$ are independently chosen for $j \neq j'$.)

As you see, the above argument depends on subtraction. So it won't work (for example) on arbitrary commutative semirings. Perhaps you could relax the multiplicative properties of the algebraic structure, and still get the result?

$\endgroup$
  • $\begingroup$ Nice, thanks. I see your point about there being a possibility of reducing the constraints on the multiplicative structure. Just for my information, isn't this the same algorithm as that in the original paper of Freivalds? $\endgroup$ – Robin Kothari Apr 8 '11 at 18:20
  • $\begingroup$ Freivalds' algorithm picks a random vector with components in {-1,1}. That works too. If you are more careful you can get the probability of success to be at least $1/2$. $\endgroup$ – Ryan Williams Apr 8 '11 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.