6
$\begingroup$

I am going to consider Freivald's algorithm in the field mod 2. So in this algorithm we want to check wether $$AB = C$$ and be correct with high probability.

The algorithm choose a random $r$ n-bit vector and if $$A(Br) = Cr$$ then outputs YES, otherwise outputs no.

I want to show that it has has one-sided success probability 1/2. For that I want to show that when $AB = C$ then the algorithm is correct with probability 1 and when $AB \neq C$ then the probability of it being correct is at least 1/2.

When $AB = C$ its clear that the algorithm is always correct because:

$$ A(Br) = (AB)r = Cr$$

So, if $AB=C$, then $A(Br)$ is always equal to $Cr$.

The case when $AB \neq C$ is a little trickier. Let $D = AB - C$. When the multiplication are not equal then $D \neq 0$. Let a good $r$ be a vector that discovers the incorrect multiplication (i.e. $D \neq 0$ and $Dr \neq 0$, multiplying by $r$ makes it still zero). let a bad $r$ be a vector that makes us mess up, i.e. conclude the multiplication is correct when is not. In other words, when $D \neq 0$ (i.e. multiplication was done correctly $AB = C$) but when we use $r$ to check this we get the wrong conclusion (i.e. $Dr = 0$, when in fact $D \neq 0$).

The high level idea of the proof is, if we can show that for every bad $r$ there is a good $r$, then half the $r$'s are good so our algorithm is about 1/2 percent of the time correct. This high level idea of the proof makes sense to me, however, what is not clear to me is the precise detail of the inequality (whether $Pr[error] \geq \frac{1}{2}$ or the other way round).

So consider the case where $D \neq 0 $ i.e. $AB \neq C$. In this case then we have that at least one entry $(i,j)$ in $D$ is not zero (its 1 cuz we are doing mod 2). Let that entry be $d_{i,j}$. Let $v$ be a vector such that it picks up that entry. i.e. $Dv \neq 0$ such that $(Dv)_{i} = d_{i,j}$. In this case, if we have a bad $r$ (i.e. an r such that when $D \neq 0$ yields $Dr = 0$ ) then we could make it into a good vector $r'$ by flipping its $i$ coordinate. i.e.

$$ r' = r +v_i$$

This mapping from Bad to Good is clearly 1 to one. i.e. it clear that the equation $ r' = r +v_i$ only maps to one unique $r'$, so it cannot be one to many. Now lets see that its not many to one either. If there was another $\tilde r$ s.t. $\tilde r = r'$ then that would mean

$$r' = r+ v_i = \tilde r + v_i \;\; (\operatorname{mod} \; 2) \implies r = \tilde r \;\; (\operatorname{mod} \; 2)$$

So its one to one. Therefore, the for each Bad $r$ there is a good $r'$. However, it is not clear to me why that would imply:

$$ Pr[A(Br) \neq C] = Pr[Dr \neq 0] \geq \frac{1}{2}$$

I see why it would be exactly equal to 1 but it is not clear to me at all why it implies the above inequality.

|cite|improve this question
$\endgroup$
6
$\begingroup$

Let $G$ be the number of good vectors, and $B$ be the number of bad vectors. The proof shows that $G \geq B$, since the mapping from the bad vectors to the good ones is one-to-one. Since all vectors are equally likely, $$ \Pr[Dr \neq 0] = \frac{G}{G+B} \geq \frac{1}{2}. $$ The last inequality is a bit of algebra I leave to you.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Sorry, I am still confused about the inequality thing. Is the proof I gave a correct proof for the equality or the inequality? I thought we wanted to show it was at least 1/2, but did my proof show its exactly 1/2? (I also added the details to show what I think 1 to 1 means). $\endgroup$ – Charlie Parker Nov 3 '15 at 16:06
  • 3
    $\begingroup$ A mapping $f$ is one-to-one if $f(x) = f(y)$ implies $x=y$. You have given a one-to-one mapping $f\colon \mathcal B \to \mathcal G$ mapping the set of bad instances to the set of good instances. Since $f$ is one-to-one, $|\mathcal G| \geq |\mathcal B|$. In fact, $f$ is a bijection, and so $|\mathcal G| = |\mathcal B|$. $\endgroup$ – Yuval Filmus Nov 3 '15 at 17:13
  • 2
    $\begingroup$ you should include that last comment in your answer. Thanks Yuval! Your answers are always so good! :D $\endgroup$ – Charlie Parker Nov 3 '15 at 21:28
  • $\begingroup$ As loup blanc mentions, in fact it is not true that $|\mathcal{G}| = |\mathcal{B}|$ in general. $\endgroup$ – Yuval Filmus Nov 8 '15 at 15:26
-1
$\begingroup$

Let $D=[d_{k,l}]$. If $d_{i,j}\not=0$, then $Prob(Dr\not=0)\geq Prob(i^{th}$ line of $Dr$ is $\not=0)=1/2$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ You should provide (only) an answer to the question. Your answer can include the fact that the probability can be arbitrarily close to 1. However, first and foremost it needs to answer the original question. $\endgroup$ – Yuval Filmus Nov 8 '15 at 17:18
  • 2
    $\begingroup$ Your post is so messy that it is hard to read. I've attempted to shape it into an answer, but I don't understand what you're writing — you don't seem to use the same notations as in the question. You should rewrite your post to be an answer to the question, not a response to Yuval's answer. If you wish to respond to Yuval's answer, post a comment on that answer. $\endgroup$ – Gilles 'SO- stop being evil' Nov 8 '15 at 17:40
  • $\begingroup$ @ Gilles , my friend, you arrive after the battle. $\endgroup$ – loup blanc Nov 8 '15 at 17:58
  • $\begingroup$ @ Gilles and I do not understand why you edit my text before I read the comments sent to me $\endgroup$ – loup blanc Nov 8 '15 at 18:00

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.