Simple algorithm takes O(n3) operations. Want to check if a given matrix multiplication program works correctly Choose a random vector r = (r1, r2, , rn) in {0,1}n. Compute A(Br) and Cr then comparer the two values: if equal return yes AB=C, else no. | Probability for Computing LECTURE 4 CONDITIONAL PROB APPLICATIONS GEOMETRIC DIS 2010 Quoc Le Van Nguyen Probability in Computing BILITY RIBUTION Agenda Application Verification of Matrix Multiplication Application Randomized Min-Cut Geometric Distribution Coupon Collector s Problem 2010 Quoc Le Van Nguyen Probability for Computing 2 Application Verifying Matrix Multiplication Consider matrix multiplication AB C integers modulo 2 Simple algorithm takes O n3 operations. Want to check if a given matrix multiplication program works correctly Randomized Algorithm Choose a random vector r r1 r2 . rn in 0 1 n. Compute A Br and Cr then comparer the two values if equal return yes Ab C else no. Note on the above randomized algorithm 1-side error Complexity O n2 Accuracy depends on P ABr Cr when AB C 2010 Quoc Le Van Nguyen Probability for Computing
