Timeline for Correctness of Freivald algorithm for checking matrix multiplication, why is the probability of checking $AB \neq C$ at least 1/2?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 8, 2015 at 15:27 | history | edited | Yuval Filmus | CC BY-SA 3.0 | deleted 130 characters in body |
| Nov 8, 2015 at 15:26 | comment | added | Yuval Filmus | As loup blanc mentions, in fact it is not true that $|\mathcal{G}| = |\mathcal{B}|$ in general. | |
| Nov 3, 2015 at 21:33 | history | edited | Yuval Filmus | CC BY-SA 3.0 | deleted 7 characters in body |
| Nov 3, 2015 at 21:28 | vote | accept | Charlie Parker | ||
| Nov 3, 2015 at 21:28 | comment | added | Charlie Parker | you should include that last comment in your answer. Thanks Yuval! Your answers are always so good! :D | |
| Nov 3, 2015 at 17:13 | comment | added | Yuval Filmus | 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|$. | |
| Nov 3, 2015 at 16:06 | comment | added | Charlie Parker | 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). | |
| Nov 3, 2015 at 6:08 | history | answered | Yuval Filmus | CC BY-SA 3.0 |