BOUNDS ON SAMPLE SPACE SIZE FOR MATRIX PRODUCT VERIFICATION

We show that the size of any sample space that could be used in Freiva lds' probabilistic matrix product verification algorithm for n x n mat rices is at least (n - 1)/epsilon if the probability of error is at mo st epsilon, matching the upper bound of Kimbrel and Sinha. We also pro vide a characterization of any sample space for which Freivalds' algor ithm has probability of error at most epsilon. We then provide a gener alization of Freivalds' algorithm and give a tight lower bound on the time-randomness tradeoff for this class of algorithms.