THE FOLD / BOSS / THE FIREWALL / THE FREIVALDS
THE FREIVALDS
verify a matrix product in O(n^2) with a random probe
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Freivalds’ algorithm checks whether a claimed matrix product A·B = C is correct in O(n2) — far faster than the O(n3) it would take to recompute A·B. The trick: pick a random 0/1 vector r and test whether A(Br) = Cr. If A·B = C the test always passes; if not, it fails with probability ≥ ½ each round, so a few rounds catch any error with overwhelming confidence. It is the seminal example of a randomized verifier.
LIT verified live: over 200 trials the correct product passes all rounds, and a product with a single wrong entry is caught within 10 rounds (window.__freivalds). FIG one-sided error: correct always passes; wrong caught with high probability.
LIT verified live: over 200 trials the correct product passes all rounds, and a product with a single wrong entry is caught within 10 rounds (window.__freivalds). FIG one-sided error: correct always passes; wrong caught with high probability.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-firewall — the guard that verifies a claim cheaply rather than redoing the work. Freivalds’ algorithm is that guard for matrix products. AVAN (AI) built the instrument: the random 0/1 probe vector, the three matrix–vector products, the pass/fail test, and the correct-always-passes / wrong-caught checks.
Credit as content: Rūsiņš Freivalds (1977). The weave: David names the firewall; I probe A(Br) against Cr with a random vector and confirm a true product always passes while a corrupted one is caught fast.
Credit as content: Rūsiņš Freivalds (1977). The weave: David names the firewall; I probe A(Br) against Cr with a random vector and confirm a true product always passes while a corrupted one is caught fast.
3 ONE DIMENSION
Instead of forming A·B (O(n3)), pick random r and compute A(Br) and Cr — three matrix×vector products (O(n2)). If they ever differ, C is wrong; each round independently catches an error with probability ≥ ½.
4 TWO DIMENSIONS · INTERACTIVE
A claimed product C (sometimes corrupted); Freivalds’ random-vector test accepts the correct one and rejects the wrong one.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a product verified without recomputing it.
AVAN’s addition (the inverse-companion): verify a matrix product in O(n2) by probing with a random vector — a correct product always passes A(Br)=Cr, a wrong one fails at least half the time, so a few rounds suffice. The inverse of ‘recompute A·B to check C’ is ‘probe with random r — cheap, one-sided, and confident.’ Magenta is the O(n3) recomputation you skip; green is the O(n2) random probe. Checking without redoing.
LIT Genuine Freivalds' algorithm (Freivalds 1977). Verified live: over 200 trials, a correct product C=A*B passes all 10 random-vector rounds, and a product with a single corrupted entry is caught (rejected) within 10 rounds (window.__freivalds.correctPasses; wrongCaught/wrongTotal).
FIG One-sided error, honestly stated: a correct product ALWAYS passes; a wrong product is caught only with high probability (>= 1/2 per round). The random 0/1 probe vector, the three matrix-vector products, the pass/fail test, and the correct-passes / wrong-caught checks run in-browser and hold. The AVAN inverse is honest — probing A(Br) against Cr with a random vector verifies the product in O(n^2); magenta is the O(n^3) recomputation skipped, green the O(n^2) probe. Checking without redoing.
FIG One-sided error, honestly stated: a correct product ALWAYS passes; a wrong product is caught only with high probability (>= 1/2 per round). The random 0/1 probe vector, the three matrix-vector products, the pass/fail test, and the correct-passes / wrong-caught checks run in-browser and hold. The AVAN inverse is honest — probing A(Br) against Cr with a random vector verifies the product in O(n^2); magenta is the O(n^3) recomputation skipped, green the O(n^2) probe. Checking without redoing.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE FIREWALL · David Lee Wise (ROOT0), with AVAN