Content deleted Content added
m Removed unneeded space before refs |
m →Definition: clarified randomness source |
||
Line 11:
In OMv, an algorithm is given an integer <math>n</math> and an <math>n\times n</math> Boolean matrix <math>M</math>. The algorithm then runs for <math>n</math> rounds, and at each round <math>i</math> receives an <math>n</math>-dimensional Boolean vector <math>v_i</math> and must return the product <math>Mv_i</math> (before continuing to round <math>i+1</math>).<ref name=":0" />
An algorithm is said to solve OMv if, with probability at least <math>2/3</math> over the randomness of the algorithm, it returns the product <math>Mv_i</math> at every round <math>i</math>.
=== Variants of OMv ===
| |||