Online Vector-Matrix-Vector Multiplication (Matrix-Vector Multiplication)

Description

Let $M$ be a binary $n \times n$ matrix than can be preprocessed. After preprocessing $n$ vector pairs $(u^1, v^1), \ldots, (u^n, v^n)$, arrive one at a time and the task is to compute $(u^i)^T M v^i$ before being presented with the $i+1$th vector pair for every $i$.

Related Problems

Related: Online Matrix-Vector Multiplication

Parameters

n: dimension of square matrix, number of vector pairs, size of vectors

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions TO Problem

Problem	Implication	Year	Citation	Reduction
Bipartite Graph MCM	assume: OMv then: there is no algorithm for solving incremental (or decremental) maximum cardinality bipartite matching with amortized time $O(n^{1-\epsilon})$ per insertion (or deletion) and $O(n^{2-\epsilon})$ time per query for any $\epsilon > {0}$	2016	https://arxiv.org/abs/1602.06705	link

References/Citation

https://arxiv.org/pdf/1602.06705.pdf