Randomized Algorithms

CS F364 — Design & Analysis of Algorithms | Summer 2026

Las Vegas vs Monte Carlo, dot-product lemma, Freivalds’ algorithm

Problem E1

Distinguish Las Vegas and Monte Carlo randomized algorithms. Give one example of each type from the course.

Solution

Las Vegas: always correct, randomized runtime (e.g., randomized quicksort). Monte Carlo: bounded error, deterministic runtime (e.g., Freivalds’ algorithm).

Problem E2

Let x \in \{0,1\}^n be a non-zero vector and let r \in \{0,1\}^n be chosen uniformly at random. Show that \Pr[\langle r, x \rangle = 0 \pmod{2}] = 1/2.

Solution

Fix any index j where x_j = 1. Write \langle r, x \rangle = r_j + S \pmod{2} where S = \sum_{i \neq j} r_i x_i. Condition on any fixing of r_i for i \neq j; then S is fixed. Exactly one choice of r_j \in \{0,1\} makes r_j + S = 0. Since r_j is independent and uniform, \Pr[\langle r, x \rangle = 0] = 1/2 regardless of S.

Problem E3

Assume the lemma from E2: for any non-zero x \in \{0,1\}^n, \Pr_r[\langle r, x \rangle = 0] = 1/2.

Use this to analyze Freivalds’ algorithm: to check AB = C, pick a random r \in \{0,1\}^n and check A(Br) = Cr.

If AB \neq C, what is the maximum probability that the test passes (false positive)?
What is the running time of Freivalds’ algorithm? How does it compare to the deterministic algorithm of computing AB and comparing to C?

Solution

If AB \neq C, then D = AB - C \neq 0. The test passes if Dr = 0. Since D \neq 0, there is at least one non-zero row d. By the lemma, \Pr[d \cdot r = 0] = 1/2. For the whole matrix, \Pr[Dr = 0] \le 1/2 (the product is zero only if every row dot product is zero, which is no more likely than any single row being zero).
Running time: compute Br (O(n^2)), then A(Br) (O(n^2)), then Cr (O(n^2)) — overall O(n^2). Deterministic: AB takes O(n^3) (naive) or O(n^{2.807}) (Strassen). Freivalds is an order of magnitude faster and can be boosted to exponentially small error with O(\log(1/\epsilon)) repetitions.