Content deleted Content added
→Conjectured hardness: added conjectured hardness as blockquote |
→Definition: added info on variants of omv |
||
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 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>.
=== Variants of OMv ===
The ''online vector-matrix-vector problem'' (OuMv) is a variant of OMv where the algorithm receives, at each round <math>i</math>, two Boolean vectors <math>u_i</math> and <math>v_i</math>, and returns the product <math>u_i M v_i</math>. This version has the benefit of returning a Boolean value at each round instead of a vector of an <math>n</math>-dimensional Boolean vector. The hardness of OuMv is implied by the hardness of OMv.<ref name=":0" />
More heavily parameterized versions of OMv are also used, where the matrix is not necessarily square and where the dimension of the vector is not necessarily equal to the number of rounds.
== Conjectured hardness ==
| |||