Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems

Recall that $M$ denotes the input matrix given for preprocessing in the $\exists$Equality-OMv problem. Let $t:=\lceil n^{\epsilon /2}\rceil$ be a parameter. For every $k\in [n]$ and every $\mathrm{\ell }\in [t]$, let $f_k^{(\mathrm{\ell })}$ be the $\mathrm{\ell }$-th most frequent value appearing in the $k$-th column of matrix $M$ (if there are less than $\mathrm{\ell }$ distinct values in the column, let $f_k^{(\mathrm{\ell })}$ be some other arbitrary integer). Note that for any value $x$ not in $\{f_k^{(1)},f_k^{(2)},\mathrm{\dots },f_k^{(t)}\}$, $x$ appears in the $k$-th column of $M$ at most $n/t$ times; we call such values rare. In the preprocessing phase, the algorithm prepares $t$ Boolean matrices $M^{(1)},M^{(2)},\mathrm{\dots },M^{(t)}\in {\{0,1\}}^{n\times n}$ defined as follows:

Then, it instantiates the hypothesized Boolean-OMv algorithm for each of these matrices separately. Finally, for each column of $M$, the algorithm prepares a dictionary mapping each rare value in that column to a list of indices under which that value appears in the column. This ends the preprocessing phase.

Upon receiving a query $v\in {\mathbb{Z}}^n$, the algorithm first initializes the output vector to all zeros. Then, for every $\mathrm{\ell }=1,\mathrm{\dots },t$, it creates the vector $v^{(l)}$ defined by

and computes the Boolean product $M^{(\mathrm{\ell })}{v}^{(\mathrm{\ell })}$, using the $\mathrm{\ell }$-th instantiation of the hypothesized Boolean-OMv algorithm. Each such product gets then element-wise OR-ed to the output vector. Finally, for every $k=1,\mathrm{\dots },n$, if $v[k]$ is a rare value in the $k$-th column of matrix $M$, the algorithm goes through the list of all indices $i$ such that $M[i][k]=v[k]$ (recall that there are at most $n/t$ of them) and for each of them sets the corresponding $i$-th entry of the output vector to $1$.

It is easy to see that whenever the algorithm sets an output entry to $1$, it is because of some pair of entries $M[i][k]$ and $v[k]$ that have the same value. Conversely, if some pair of entries $M[i][k]$ and $v[k]$ have the same value, then either it is a frequent value and some $M^{(\mathrm{\ell })}{v}^{(\mathrm{\ell })}$ contributes a $1$, or it is a rare value and gets manually matched.

Let us analyze the running of our $\exists$Equality-OMv algorithm. There are $t$ instantiations of the hypothesized Boolean-OMv algorithm, which require $O(t{n}^{3-\epsilon })$ time in total. Then, going through all rare values takes at most $O(n^2/t)$ time per $v_j$, and thus $O(n^3/t)$ time for all $n$ queries. This adds up to total time $O(t{n}^{3-\epsilon }+n^3/t)$. By choosing $t:=\lceil n^{\epsilon /2}\rceil$ we get the claimed running time $O(n^{3-(\epsilon /2)})$. $◀$

Let $t:=\lceil n^{\epsilon /2}\rceil$ be a parameter. For every $i\in [n]$, let $R_i$ be the sorted $i$-th row of the input matrix $M$. Consider partitioning each $R_i$ into $t$ buckets of consecutive elements, with at most $\lceil n/t\rceil$ elements per bucket. For every $\mathrm{\ell }\in [t]$, let $M^{(\mathrm{\ell })}\in {(\mathbb{Z}\cup \{\mathrm{\infty }\})}^{n\times n}$ be the matrix defined as follows:

Note that each row of $M^{(\mathrm{\ell })}$ contains $\mathrm{\Theta }(n/t)$ finite entries.⁴⁴4If there are multiple entries with the same value, they may land in different buckets.

In the preprocessing phase, the algorithm instantiates the hypothesised $\exists$Dominance-OMv algorithm for each of the matrices $M^{(1)},M^{(2)},\mathrm{\dots },M^{(\mathrm{\ell })}$, and also for the matrix $M$.⁵⁵5Formally, the $\exists$Dominance-OMv algorithm may not accept infinite entries in the input, but we can replace each $\mathrm{\infty }$ with $W+2$, where $W$ denotes the largest absolute value of any entry in $M$, and each entry greater than $W$ in any query vector with $W+1$.

Upon receiving a query $v\in {\mathbb{Z}}^n$, the algorithm proceeds to compute the product $M\begin{array}{c}\text{<span class="ltx\_inline-block ltx\_markedasmath ltx\_align\_bottom"> <span class="ltx\_p"> <span class="ltx\_inline-block ltx\_transformed\_outer" style="width:7.5pt;height:6.7pt;vertical-align:-1.5pt;"><span class="ltx\_transformed\_inner" style="transform:translate(-1.3pt,1.1pt) scale(0.75,0.75) ;"> <span class="ltx\_p"><xmath xmlns="http://dlmf.nist.gov/LaTeXML"><xmtok name="bigcirc" role="MULOP">○</xmtok></xmath></span> </span></span></span> </span>}\hfill \\ \text{<div class="ltx\_inline-block ltx\_transformed\_outer" style="width:4.5pt;height:3.8pt;vertical-align:-0.0pt;"><span class="ltx\_transformed\_inner" style="transform:translate(-1.1pt,0.9pt) scale(0.675,0.675) ;"> <p class="ltx\_p"><xmath xmlns="http://dlmf.nist.gov/LaTeXML"><xmtok meaning="or" name="lor" role="ADDOP">∨</xmtok></xmath></p> </span></div>}\hfill \end{array}v$ in two steps. First, for every $i\in [n]$, it computes the minimum $M[i,k]$ such that $M[i,k]⩾v[k]$, and stores the results in a column vector $u$. Second, for every $i\in [n]$, it computes the minimum $v[k]$ such that $v[k]⩾M[i,k]$, and stores the results in a column vector $w$. At the very end the algorithm computes $(M\begin{array}{c}\text{<span class="ltx\_inline-block ltx\_markedasmath ltx\_align\_bottom"> <span class="ltx\_p"> <span class="ltx\_inline-block ltx\_transformed\_outer" style="width:7.5pt;height:6.7pt;vertical-align:-1.5pt;"><span class="ltx\_transformed\_inner" style="transform:translate(-1.3pt,1.1pt) scale(0.75,0.75) ;"> <span class="ltx\_p"><xmath xmlns="http://dlmf.nist.gov/LaTeXML"><xmtok name="bigcirc" role="MULOP">○</xmtok></xmath></span> </span></span></span> </span>}\hfill \\ \text{<div class="ltx\_inline-block ltx\_transformed\_outer" style="width:4.5pt;height:3.8pt;vertical-align:-0.0pt;"><span class="ltx\_transformed\_inner" style="transform:translate(-1.1pt,0.9pt) scale(0.675,0.675) ;"> <p class="ltx\_p"><xmath xmlns="http://dlmf.nist.gov/LaTeXML"><xmtok meaning="or" name="lor" role="ADDOP">∨</xmtok></xmath></p> </span></div>}\hfill \end{array}v)[i]=\min \{u[i],w[i]\}$, for every $i\in [n]$.

In order to compute $u$, the algorithm first asks for the dominance products , for all $\mathrm{\ell }\in [t]$. Then, for each $i=1,\mathrm{\dots },n$, the algorithm finds the smallest $\mathrm{\ell }$ such that , which corresponds to finding the first bucket in $R_i$ containing an element greater⁶⁶6This is because the entries in $M^{(\mathrm{\ell })}$ and $-v$ are negated. than or equal to the corresponding element in $v$. Hence, the algorithm can scan the elements in this bucket and pick the smallest one that is larger than or equal to the corresponding element in $v$; this element is then stored in $u[i]$.

Let us analyze the cost of computing $u$’s over the span of $n$ queries. The $t$ dominance products require time $O(t{n}^{3-\epsilon })$ in total. On top of that, for each of the $n$ queries and for each of the $n$ output coordinates, the algorithm scans one bucket of size $\mathrm{\Theta }(n/t)$, which takes time $O(n^3/t)$ in total. All together, the algorithm spends time $O(t{n}^{3-\epsilon }+n^3/t)=O(n^{3-(\epsilon /2)})$ on computing $u$’s.

Next, it is almost symmetric to calculate $w$. The algorithm sorts the entries of $v$ into an ordered list $S$, and partitions $S$ into $t$ buckets, with at most $\lceil n/t\rceil$ elements per bucket. For each bucket $\mathrm{\ell }\in [t]$, the algorithm computes the dominance product , where $v^{(\mathrm{\ell })}\in {(\mathbb{Z}\cup \{-\mathrm{\infty }\})}^n$ is the column vector such that

Then, for each $i=1,\mathrm{\dots },n$, the algorithm looks for the smallest $\mathrm{\ell }$ such that , and scans the elements in the $\mathrm{\ell }$-th bucket looking for the smallest $v[k]$ that is greater than or equal to the corresponding $M[i,k]$. By the same argument as before, computing all $w$’s takes time $O(n^{3-(\epsilon /2)})$. $◀$

First, for any pair $(i,j)\in [n]\times [n]$, due to rounding down we have

Now, suppose that $k$ is a witness for $u[i]$, and $l$ is a witness for $\widehat{u}[i]$, i.e., $M[i,k]+v[k]=u[i]$, and $\widehat{M}[i,l]+\widehat{v}[l]=\widehat{u}[i]$. We derive that

Therefore, we have . Since the matrix entries all take integer values, we have that if $k\in [n]$ is a witness for $u[i]$, then it must satisfy that $\widehat{M}[i,k]+\widehat{v}[k]\in \{\widehat{u}[i],\widehat{u}[i]+1\}$, i.e., $k\in C_i$. $◀$

Now we argue that small sets of candidates can be enumerated efficiently.

We consider four cases, based on the direction of the monotonicity:

In this case also the columns of $\widehat{M}$ are monotone, and their entries are bounded by $\lfloor n/\mathrm{\Delta }\rfloor$. The algorithm uses a self-balancing binary search tree (BST) to maintain, while $i$ iterates from $1$ to $n$, the set of pairs

Computing $\widehat{u}[i]$ is the standard tree operation of querying for the minimum. Moreover, the BST can report the number of elements smaller than a certain value in time $O(\log n)$, and enumerate them in time proportional to that number. This allows the algorithm to determine the size of $C_i$ quickly, and enumerate it if it is small. As $i$ iterates from $1$ to $n$, the algorithm only needs to update the elements where there is an increase (or decrease) from $\widehat{M}[i,k]$ to $\widehat{M}[i+1,k]$. In each column of $M$ there are at most $n/\mathrm{\Delta }$ such changes, thanks to the boundedness and monotonicity.⁸⁸8The locations of all such changes can be, e.g., precomputed before processing any query, or computed during each query using binary search in time $O(\log n)$ per each location. Therefore the total number of updates over the $n$ iterations is at most $n^2/\mathrm{\Delta }$, and each update takes time $O(\log n)$. The time spent on listing elements of $C_i$ (for all $i$) is $O(n\log n+n^2/\mathrm{\Delta })$.

This case is very similar to the previous one. The algorithm maintains (over the span of $n$ queries) a separate BST for each $i$, and uses it to compute $(\widehat{M}\oplus {\widehat{v}}_j)[i]$ for all $j$’s. When there is an increase (or decrease) from ${\widehat{v}}_j[k]$ to ${\widehat{v}}_{j+1}[k]$, the algorithm has to update an element in all $n$ trees, but this happens at most $n/\mathrm{\Delta }$ times for each $k$, so $n^2/\mathrm{\Delta }$ times for all $k$’s. Hence, the total time spent on such updates over the course of $n$ queries is $O(n^3\log n/\mathrm{\Delta })$, and the amortized time per query is $O(n^2\log n/\mathrm{\Delta })$.

Due to the monotonicity, we can think of the $i$-th row of $\widehat{M}$, for each $i=1,\mathrm{\dots },n$, as consisting of $\lfloor n/\mathrm{\Delta }\rfloor +1$ contiguous blocks $K_i^{(0)},K_i^{(1)},\mathrm{\dots },K_i^{(\lfloor n/\mathrm{\Delta }\rfloor )}\subseteq [n]$ of identical entries, i.e., $\forall k\in K_i^{\left(x\right)}M[i,k]=x$. Upon receiving a query vector $v$, the algorithm builds (in linear time) a range minimum query (RMQ) data structure (see, e.g., [3]) in order to compute in constant time the minimum entry of $\widehat{v}$ in each of the $O(n^2/\mathrm{\Delta })$ blocks, i.e., $\widehat{v}[[K_i^{(x)}]]:=\min \{\widehat{v}[k]\mid k\in K_i^{(x)}\}$. Adding each of these minima to their corresponding values from $\widehat{M}$ gives a list of candidate values for $\widehat{u}[i]$’s, i.e.,

Thus, we already know how to compute $\widehat{u}$ is time $O(n^2/\mathrm{\Delta })$. Now let us explain how to extend this idea to also list elements of all small enough $C_i$’s. For each value that appears in $\widehat{v}$, the algorithm calculates the sorted sequence of indices under which this value appears in $\widehat{v}$. This allows computing in time $O(\log n)$ how many times a given value appears in a given range of indices in $\widehat{v}$; indeed, it boils down to performing two binary searches of the two endpoints of the range in the sequence corresponding to the given value. Furthermore, all these appearances can be enumerated in time proportional to their count. For each block $K_i^{(x)}$ such that $x+\widehat{v}[[K_i^{(x)}]]=\widehat{u}[i]$ the algorithm enumerates all appearances of $\widehat{v}[[K_i^{(x)}]]$ and $\widehat{v}[[K_i^{(x)}]]+1$ in the range $K_i^{(x)}$ in $\widehat{v}$, and adds them to $C_i$. If the total size of $C_i$ would exceed $n/\mathrm{\Delta }$, the algorithm stops the enumeration and proceeds to the next block. Similarly, for each block such that $x+\widehat{v}[[K_i^{(x)}]]=\widehat{u}[i]+1$ the algorithm enumerates all appearances of $\widehat{v}[[K_i^{(x)}]]$.

This case is symmetric to the previous one. The difference is that now the algorithm splits $\widehat{v}$ into $O(n/\mathrm{\Delta })$ blocks, and prepares an RMQ data structure for each row of $\widehat{M}$. $◀$

Now we are ready to present our subcubic algorithm for Bounded Monotone Min-Plus OMv, assuming a subcubic algorithm for $\exists$Equality-OMv.

In the preprocessing, the algorithm samples uniformly and independently at random a set $R\subseteq [n]$ of columns of $M$, of size $|R|:=\lceil 3\mathrm{\Delta }\ln n\rceil$. For each $r\in R$, the algorithm prepares an $\exists$Equality-OMv data structure for matrix $M^{(r)}$ obtained from $M$ by subtracting the $r$-th column from all the columns, i.e.,

The algorithm handles each query in two independent steps. The goal of the first step is to compute $u[i]$ for those $i$ that have $|C_i|⩽n/\mathrm{\Delta }$, and the goal of the second step is to compute $u[i]$ for $i$ with $|C_i|>n/\mathrm{\Delta }$.

For each $i\in [n]$, the algorithm either finds out that $|C_i|>n/\mathrm{\Delta }$, or lists all elements of $C_i$ and then computes $u[i]={\min }_{k\in C_i}(M[i,k]+v[k])$. By Lemma 14, this takes time $O(n^2\log n/\mathrm{\Delta })$, for all $i$’s in total. The correctness of this step follows from Lemma 13.

In the second step, the algorithm must compute the remaining $u[i]$’s, i.e., those for which $C_i$’s contain too many elements to be handled in the first step. To this end, for every $r\in R$ and every $\delta \in \{0,1,\mathrm{\dots },3\mathrm{\Delta }-2\}$ the algorithm computes the equality product $M^{(r)}\begin{array}{c}\text{<span class="ltx\_inline-block ltx\_markedasmath ltx\_align\_bottom"> <span class="ltx\_p"> <span class="ltx\_inline-block ltx\_transformed\_outer" style="width:7.5pt;height:6.7pt;vertical-align:-1.5pt;"><span class="ltx\_transformed\_inner" style="transform:translate(-1.3pt,1.1pt) scale(0.75,0.75) ;"> <span class="ltx\_p"><xmath xmlns="http://dlmf.nist.gov/LaTeXML"><xmtok name="bigcirc" role="MULOP">○</xmtok></xmath></span> </span></span></span> </span>}\hfill \\ \text{<div class="ltx\_inline-block ltx\_transformed\_outer" style="width:5.3pt;height:2.5pt;vertical-align:-0.0pt;"><span class="ltx\_transformed\_inner" style="transform:translate(-1.3pt,0.6pt) scale(0.675,0.675) ;"> <p class="ltx\_p">=</p> </span></div>}\hfill \end{array}-(v-v[r]+\delta )$. For every $i\in [n]$, if $(M^{(r)}\begin{array}{c}\text{<span class="ltx\_inline-block ltx\_markedasmath ltx\_align\_bottom"> <span class="ltx\_p"> <span class="ltx\_inline-block ltx\_transformed\_outer" style="width:7.5pt;height:6.7pt;vertical-align:-1.5pt;"><span class="ltx\_transformed\_inner" style="transform:translate(-1.3pt,1.1pt) scale(0.75,0.75) ;"> <span class="ltx\_p"><xmath xmlns="http://dlmf.nist.gov/LaTeXML"><xmtok name="bigcirc" role="MULOP">○</xmtok></xmath></span> </span></span></span> </span>}\hfill \\ \text{<div class="ltx\_inline-block ltx\_transformed\_outer" style="width:5.3pt;height:2.5pt;vertical-align:-0.0pt;"><span class="ltx\_transformed\_inner" style="transform:translate(-1.3pt,0.6pt) scale(0.675,0.675) ;"> <p class="ltx\_p">=</p> </span></div>}\hfill \end{array}-(v-v[r]+\delta ))[i]$=1, then there must exist $k\in [n]$ such that

and hence

The algorithm therefore adds $M[i,r]+v[r]-\delta$ to the list of possible values for $u[i]$, and at the end of the process it sets each $u[i]$ to the minimum over those values.

We now argue that if $R\cap C_i\ne \mathrm{\varnothing }$ (which holds with high probability when $|C_i|>n/\mathrm{\Delta }$ via a standard hitting set argument, see below), then the algorithm correctly computes $u[i]$ in the second step. Indeed, pick $r\in R\cap C_i$ and let $k\in [n]$ be a witness for $(M\oplus v)[i]$, i.e., $M[i,k]+v[k]=(M\oplus v)[i]$. Let $\delta :=(M[i,r]+v[r])-(M[i,k]+v[k])$. Clearly, $(M^{(r)}\begin{array}{c}\text{<span class="ltx\_inline-block ltx\_markedasmath ltx\_align\_bottom"> <span class="ltx\_p"> <span class="ltx\_inline-block ltx\_transformed\_outer" style="width:7.5pt;height:6.7pt;vertical-align:-1.5pt;"><span class="ltx\_transformed\_inner" style="transform:translate(-1.3pt,1.1pt) scale(0.75,0.75) ;"> <span class="ltx\_p"><xmath xmlns="http://dlmf.nist.gov/LaTeXML"><xmtok name="bigcirc" role="MULOP">○</xmtok></xmath></span> </span></span></span> </span>}\hfill \\ \text{<div class="ltx\_inline-block ltx\_transformed\_outer" style="width:5.3pt;height:2.5pt;vertical-align:-0.0pt;"><span class="ltx\_transformed\_inner" style="transform:translate(-1.3pt,0.6pt) scale(0.675,0.675) ;"> <p class="ltx\_p">=</p> </span></div>}\hfill \end{array}-(v-v[r]+\delta ))[i]$=1, so it only remains to show that $\delta \in \{0,1,\mathrm{\dots },3\mathrm{\Delta }-2\}$. Obviously, $\delta ⩾0$, because $k$ minimizes $M[i,k]+v[k]$. Now let us upper bound the offset $\delta$. Since $r\in C_i$, we have $\widehat{M}[i,r]+\widehat{v}[r]⩽\widehat{u}[i]+1$, and hence

Moreover, $\widehat{M}[i,k]+\widehat{v}[k]⩾\widehat{u}[i]$, and therefore

We conclude that $\delta ⩽(\mathrm{\Delta }\widehat{u}[i]+3\mathrm{\Delta }-2)-\mathrm{\Delta }\widehat{u}[i]=3\mathrm{\Delta }-2$, as required.

It remains to analyze the success probability of the whole algorithm. For a fixed output index $i\in [n]$ such that $|C_i|>n/\mathrm{\Delta }$, the probability that the algorithm failed to sample an element $r$ from $C_i$ in all $|R|=\lceil 3\mathrm{\Delta }\ln n\rceil$ rounds is at most . By a union bound over all $n$ output indices for each of the $n$ queries, the algorithm succeeds to correctly compute all $n^2$ output entries with probability at least $1-n^2/n^3=1-1/n$.

The first step of each query (Lemma 14) takes time $O(n^2\log n/\mathrm{\Delta })$, summing up to $O(n^3\log n/\mathrm{\Delta })$ for all $n$ queries. Regarding the second step, for each query the algorithm computes $O(|R|\mathrm{\Delta })=O({\mathrm{\Delta }}^2\log n)$ equality matrix-vector products, and over the course of $n$ queries this takes time $O(n^{3-\epsilon }{\mathrm{\Delta }}^2\log n)$. The total running time is therefore $O(n^3\log n/\mathrm{\Delta }+n^{3-\epsilon }{\mathrm{\Delta }}^2\log n)=O(n^{3-(\epsilon /3)}\log n)$. $◀$