Content deleted Content added
→Definition: defined correctness |
m clarified that vector is boolean |
||
Line 8:
== Definition ==
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 <math>\mathcal{A}</math> is said to solve OMv if, with probability at least <math>2/3</math>, it returns the product <math>Mv_i</math> at every round <math>i</math>.
| |||