Let s say we have an algorithm that takes as input 3 matrix A,B and C

$$ \text{Input} :A,B,C \in Mat(n\times n)$$ $$\text{Question} :\text{is } A\cdot B=C$$

the algorith works as follow ;

$$ \text{if }(A\cdot B)_{ij}=C_{ij} \Rightarrow A\cdot B=C $$ $$ \text{if }(A\cdot B)_{ij} \neq C_{ij} \Rightarrow A\cdot B \neq C $$

with random chosen $i$ and $j$ .

I have to find in this case the error probrabilty. Can someone please give me some hints.

This problem looks a bit like the freivalds algorithm, somehow i think i have to drive a trick with it so solve mine but i am not sure .

  • 1
    $\begingroup$ Well, $C$ could be wrong on a single entry, so the error probability could be quite large. $\endgroup$ – Yuval Filmus Oct 31 '18 at 16:19
  • $\begingroup$ yeah but how much , i am guessing by 0.5 $\endgroup$ – Mohbenay Oct 31 '18 at 16:21
  • $\begingroup$ Don’t guess, calculate. $\endgroup$ – Yuval Filmus Oct 31 '18 at 16:22
  • $\begingroup$ Use the definition of probability. Count the number of elements to choose and the size of the space. Distinguish the cases where the answer is yes and the answer is no and output the smaller probability among both. $\endgroup$ – narek Bojikian Dec 26 '19 at 2:27

If I create the matrix C by calculating AB, then change a single entry in C, then you need to calculate x% of all entries to have an x% chance to find the incorrect entry.

If I change an entry in A or B, then you just need to calculate 2n entries ( but the right ones) to find AB != C.

So really your question is unanswerable until you get more information about A, B and C.


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.