Content deleted Content added
→Conjectured hardness: added info on naive alg |
→Definition: defined correctness |
||
Line 9:
== 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 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>.
== Conjectured hardness ==
| |||