Consider the following Online Boolean Matrix-Vector Multiplication problem:
We are given an $n\times n$ matrix $M$ and will receive $n$ column-vectors of
size $n$, denoted by $v_1,\ldots,v_n$, one by one. After seeing each vector
$v_i$, we have to output the product $Mv_i$ before we can see the next vector.
A naive algorithm can solve this problem using $O(n^3)$ time in total, and its
running time can be slightly improved to $O(n^3/\log^2 n)$ [Williams SODA'07].
We show that a conjecture that there is no truly subcubic ($O(n^{3-\epsilon})$)
time algorithm for this problem can be used to exhibit the underlying
polynomial time hardness shared by many dynamic problems. For a number of
problems, such as subgraph connectivity, Pagh's problem, $d$-failure
connectivity, decremental single-source shortest paths, and decremental
transitive closure, this conjecture implies tight hardness results. Thus,
proving or disproving this conjecture will be very interesting as it will
either imply several tight unconditional lower bounds or break through a common
barrier that blocks progress with these problems. This conjecture might also be
considered as strong evidence against any further improvement for these
problems since refuting it will imply a major breakthrough for combinatorial
Boolean matrix multiplication and other long-standing problems if the term
"combinatorial algorithms" is interpreted as "non-Strassen-like algorithms"
[Ballard et al. SPAA'11]. The conjecture also leads to hardness results for
problems that were previously based on diverse problems and conjectures, such
as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and
multiphase, thus providing a uniform way to prove polynomial hardness results
for dynamic algorithms; some of the new proofs are also simpler or even become
trivial. The conjecture also leads to stronger and new, non-trivial, hardness
results.

探索使用次立方算法解决在线布尔矩阵向量乘法问题的困难程度，并将此问题与许多动态问题的困难程度联系起来，以展示它们之间的多项式时间困难性，并可能为它们展示深入的无条件下界或突破共同的障碍，并为一些未解决的问题提供了一个新的，统一的证明方法。