text:
\section{Introduction}

The \textbf{Min-Plus Product} $C$ between two $n \times n$ matrices $A$ and $B$ is defined as the $n \times n$ matrix $C = A \star B$ with entries $C_{i, j} = \min_{k \in [n]} \{A_{i, k} + B_{k, j}\}$ for all $i, j \in [n]$. The naive algorithm computes $C$ in $O(n^3)$ time while the currently fastest algorithm by \citet{fastAPSP, fastAPSP_journal} runs in time $n^3/2^{\Theta(\sqrt{\log n})}$. However, since the All Pairs Shortest Path (APSP) problem is equivalent to the Min-Plus Product, under the APSP Hypothesis there is no algorithm solving Min-Plus Product in truly subcubic running time of $O(n^{3 - \epsilon})$ for some $\epsilon > 0$. Nevertheless, it is sometimes possible to break that barrier if we assume some structure on the matrices. In their recent breakthrough paper, \citet{chi2022faster} show that if $B$ has monotone rows then one can solve the Min-Plus Product in time $\Tilde O(n^{\frac{3 + \omega}{2}})$\footnote{We use the notation $\Tilde{O}$ to hide a polylogarithmic factor.}, where $\omega$ is the exponent of fast matrix multiplication. This improves upon the previously best known algorithm by \citet{polak} for Square Monotone Min-Plus Product which had a running time of $\Tilde O (n^\frac{12 +\omega}{5})$.

Fortunately, Min-Plus Product, as a fundamental problem, can be used to solve many other applications in which it is enough to assume that one of the matrices is monotone. Therefore the result of \citeauthor{chi2022faster} yields improvements for several applications. A direct consequence is for example the improvement of algorithms solving the Language Edit Distance, RNA-folding and Optimum Stack Generation problems, which where reduced to square Monotone Min-Plus Product by \citet{rna_led_osg}. However there are several other applications of Monotone Min-Plus Product in which the matrices are rectangular: the Single Source Replacement Path (SSRP) with bounded edge-weights (\ccite{polak}), Batch Range Mode (\ccite{sandlund_rangemode}), $k$-Dyck Edit Distance (\ccite{dyck}), as well as a 2-approximation of APSP (\ccite{apsp_approx}).
Even though the techniques used in \cite{chi2022faster} to solve Square Monotone Min-Plus Product seem to be applicable for rectangular matrices, a generalization of the algorithm is not straightforward and needs to be done carefully. In this paper we show the generalization for the rectangular case and then improve the running time for the above mentioned problems. We also improve the running time for Unweighted Tree Edit Distance, which was reduced to Square Monotone Min-Plus Product by \citet{treeED}, using the algorithm by \citet{chi2022faster}.

\begin{table*}[htbp]
    \centering
    \begin{threeparttable}
    \caption{Improved bounds of the expected running time (in $\Tilde{O}$) of randomized algorithms solving applications of Monotone Min-Plus Product. The improvements are resulting from \cref{thm:fast_rect} and are further discussed in Section \ref{sec:applications}. When possible we express the bound as a function of $\omega$, otherwise we use the current best bound on fast matrix multiplication \cite{gall_square} and fast rectangular matrix multiplication \cite{gall_rect}.}
    \label{fig:table_applications}
    \begin{tabular}{ @{}lll@{} }
     \toprule
     Problem & Previous bound & Improved bound \\
     \midrule
        $M$-bounded SSRP \cite{polak} & $M^{\frac{5}{17 - \omega}} n^{\frac{36 - 7 \omega}{17 - 4\omega}}$ or $M^{0.8043} n^{2.4957}$  & $M^{\frac{2}{5 - \omega}} n^{\frac{9 - \omega}{5 - \omega}}$ or $M^{0.8825} n^{2.4466}$ \\
        Batch Range Mode \cite{sandlund_rangemode, polak} & $n^{\frac{21 + 2\omega}{15 + \omega}} \leq n^{1.4820}$ & $n^{\frac{3 + 2\omega}{3 + \omega}} \leq n^{1.4416}$ \\
        $k$-Dyck Edit Distance \cite{dyck} & $n + k^{4.7820}$ & $n + k^{\frac{5}{2} + \omega(1/2)} \leq n + k^{4.5442}$ \\
        $2$-approximation APSP \cite{apsp_approx} & $n^{2.2867}$ & $n^{2.2593}$ \\
        Unweighted Tree Edit Distance \cite{treeED} & $n\cdot m^{1.9541}$ & $n \cdot m^\frac{3\omega + 7}{\omega + 5} \leq n \cdot m^{1.9149}$ \\
     \bottomrule
    \end{tabular}
    \footnotesize
    \end{threeparttable}
\end{table*}

\paragraph{Definitions}
We restrict ourselves to integer matrices only. A matrix $X$ is said to be \textbf{monotone} if each row is a non-decreasing sequence and every entry is non-negative and bounded by $O(n^\mu)$ for some $\mu \geq 0$.
When the monotonicity holds for the columns we call the matrix column-monotone.
We also consider Min-Plus Product between rectangular matrices $A$ and $B$ of dimensions $n \times n^\beta$ and $n^\beta \times n$ for some $\beta \geq 0$. Define $\omega(\beta)$ to be the \textbf{exponent of fast rectangular matrix multiplication} between two matrices of dimensions $n \times n^\beta$ and $n^\beta \times n$. So $\omega = \omega(1)$. We focus on the \textbf{Rectangular Monotone Min-Plus Product} parameterized by $(\beta, \mu)$, which is the Min-Plus Product between matrices $A$ and $B$ of dimensions $n \times n^\beta$ and $n^\beta \times n$ where $B$ is monotone with non-negative entries bounded by $O(n^\mu)$.

\paragraph{Results}
Our contribution is two fold. First we provide
an algorithm computing the Rectangular Monotone Min-Plus Product in time $\Tilde O(n^{\frac{1 + \beta + \mu + \omega(\beta)}{2}})$, as stated in \cref{thm:fast_rect}. We remark that the algorithm directly generalizes the algorithm provided by \citet{chi2022faster} for the special setting $\beta = \mu = 1$ and that in that case one falls back on their results. Next, we detail how the result of \cref{thm:fast_rect} is used to improve running times of $M$-bounded SSRP, Batch Range Mode, $k$-Dyck Edit Distance, 2-approximation of APSP. Indeed in those applications the dependency on the Monotone Min-Plus Product is not direct but depends on some parameters that need to be optimized according to the new running time given by \cref{thm:fast_rect}. We also simplify and improve the running time for Unweighted Tree Edit Distance. The improved bounds are summarized in \cref{fig:table_applications}. Additionally, we discuss one consequence of \citeauthor{chi2022faster}'s algorithm for the lower bound of SSRP algorithms.

\begin{restatable}{theorem}{genalgo}
    \label{thm:fast_rect}
    Let $\beta, \mu$ be non-negative real numbers. There is a randomized algorithm that computes the Min-Plus Product $A \star B$ with expected running time $\Tilde{O}(n^{\frac{1 + \beta + \mu + \omega(\beta)}{2}})$, where $A$ is an $n \times n^\beta$ integer matrix and $B$ is an $n^\beta \times n$ integer monotone matrix with non-negative entries bounded by $O(n^\mu)$.
\end{restatable}

\paragraph{Monotone and Bounded-Difference Min-Plus Product}
Strict\-ly speaking, except for SSRP and Batch Range Mode, the above mentioned applications don't use Monotone Min-Plus Product but Bounded-Difference Min-Plus Product. A matrix $X$ is \textbf{$\delta$-bounded-difference} (or simply bounded-difference if $\delta$ is a constant) if $|X_{i, j} - X_{i, j+1}| \leq \delta$ and $|X_{i, j} - X_{i + 1, j}| \leq \delta$ for all $i, j$. One can reduce a $\delta$-bounded difference matrix $X$ to a monotone matrix $X'$ in quadratic time by setting $X'_{i, j} = X_{i, j} + \delta j - X_{1, 1}$ for all $i, j$. In that case elements of $X'$ are non-negative and bounded by $O(n\delta)$.
In most of the above mentioned applications, a Min-Plus Product is performed between two bounded-difference matrices. This means that a stronger structure is assumed on the matrices than just the monotonicity of one matrix and this could allow for faster algorithms. In fact, before the recent result of \citet{chi2022faster} (and its generalization via \cref{thm:fast_rect}), the best known algorithm by \citet{rna_led_osg} for Square Bounded-Difference Min-Plus Product had a running time of $\Tilde O(n^{2.8244})$, while the best known algorithm by \citet{polak} for square Monotone Min-Plus Product (when $\mu=1$) had a running time of $\Tilde O(n^{2.8653})$. However \cref{thm:fast_rect} improves on both of those bounds and thus improves the running time for both Monotone and Bounded-Difference Min-Plus Product.

\paragraph{Related work}
There exist other problems such as Dynamic Range Mode (\ccite{polak}), 3SUM+ and 3SUM+ in preprocessed universe (\ccite{lewenstein_chan}) that were solved using ideas of Min-Plus Product. However for those problems the Min-Plus Product is not used as a black-box and hence our result does not directly imply an improvement.

Finally, we would like to mention that \citeauthor{chi2022faster} also solve Monotone Min-Plus Convolution in $\Tilde O(n^{1.5})$ time with the same technique in \cite{chi2022faster}. This is a major improvement upon the previously $\Tilde{O}(n^{1.869})$ time algorithm by \citet{lewenstein_chan}. Since Binary Jumbled Indexing (or Histogram Indexing) can be reduced to Monotone Min-Plus Convolution in quadratic time (see \citet{lewenstein_chan}), this also directly yields an $\Tilde O(n^{1.5})$ time algorithm for it. Additionally, earlier this year \citet{knapsack} used \citeauthor{chi2022faster}'s result to get new running times for Knapsack.

\section{Rectangular Monotone Min Plus Product}
\label{sec:algo}
In this section we reformulate and generalize the algorithm presented by \citet{chi2022faster} to compute the Monotone Min-Plus Product for arbitrary $\beta, \mu \geq 0$, thus proving \cref{thm:fast_rect}. We recall that all the ideas of the presented algorithm are from \citet{chi2022faster} and that the only novelty is to extend the setting of the matrices. We also like to note that the following algorithm can be adapted to solve Min-Plus Product when $B$ is column-monotone instead of row-monotone by using the same method as explained by \citeauthor{chi2022faster} in \cite[Appendix A]{chi2022faster}. Also, since $(A \star B)^T = B^T \star A^T$, this algorithm can be used if $A$ is column- or row-monotone.

The algorithm uses the \textbf{segment tree} data structure which allows for a sequence of integers $S = \{s_1, \dots s_n\}$ to perform the following update and query operations in $O(\log n)$ deterministic worst-case time. An update on $S$ is defined by an interval $[i, j] \subset [n]$ and an integer $u$ and updates $s_l \gets \min\{s_l, u\}$ for each $l \in [i, j]$. A query operation returns the current value of an arbitrary element $s_l$.
We will also \textbf{multiply matrices of polynomials}: if $A$ and $B$ are matrices of polynomials of degree at most $d$ and of dimensions $n \times n^\beta$ and $n^\beta \times n$, then we can compute the product $A \cdot B$ in $\Tilde O(d n^{\omega(\beta)})$ time using Fast Fourier Transform and fast matrix multiplication.

\paragraph{Overview}
Let $A$ and $B$ be two matrices of dimensions $n \times n^\beta$ and $n^\beta \times n$ such that $B$ is monotone and with entries bounded by $O(n^\mu)$. The idea of the algorithm is to divide the matrix $C = A \star B$ into two matrices $C^*$ and $\Tilde{C}$ such that $C^*_{i, j} = \lfloor C_{i, j} / p \rfloor$ and $\Tilde{C}_{i, j} = C_{i, j} \mod p$ for some integer $p$ that we describe later. This way, the original value $C_{i, j}$ can be computed by $p \cdot C^*_{i, j} + \Tilde{C}_{i, j}$.
To efficiently compute the quotient matrix $C^* = \lfloor C /p \rfloor$, we will construct matrices $A^* = \lfloor A /p \rfloor$ and $B^* = \lfloor B /p \rfloor$ and use a combinatorial approach to determine the entries of $C^*$.

The computation of the remainder matrix $\Tilde{C} = (C \mod p)$ is more complex. We will proceed iteratively, each step computing one bit of $\Tilde{C}$. For that, we define $h$ to be such that $2^{h-1} \leq p < 2^h$ and for each $l = h, h-1, \dots, 0$ let $A^{(l)} = \left\lfloor \frac{A \mod p}{2^l} \right\rfloor$ and $B^{(l)} = \left\lfloor \frac{B \mod p}{2^l} \right\rfloor$. We then construct a matrix $C^{(l)}$ approximating $\left\lfloor \frac{C \mod p}{2^l} \right\rfloor$ such that in the end $C^{(0)} = \Tilde{C}$. Note that $C^{(l)}$ will not be the Min-Plus Product $A^{(l)} \star B^{(l)}$, as this would be too costly, but is only an approximation of it. $C^{(l)}$ is computed using $C^{(l+1)}, A^{(l + 1)}, B^{(l + 1)}, A^{(l)}$ and $B^{(l)}$. \cref{lemma:filter} ensures that the correct $C^{(l)}_{i, j}$ is equal to the sum $A^{(l)}_{i, k} + B^{(l)}_{k, j}$ for some $k$ satisfying both conditions:
\begin{itemize}
    \item $A^{(l + 1)}_{i, k} + B^{(l + 1)}_{k, j} = C^{(l+1)}_{i, j} + b \text{ for some } b \in \{-10, \dots, 10\}$
    \item $A_{i, k}^{*} + B^*_{k, j} = C^*_{i, j}$
\end{itemize}
The algorithm first focuses on the first condition, and then removes all candidates that don't satisfy the second condition. In fact,  terms  $A^{(l)}_{i, k} + B^{(l)}_{k, j}$ satisfying the first conditio can be filtered out by using a common polynomial multiplication trick: construct two matrices of polynomials $A^p, B^p$ on two variables $x$ and $y$ such that for any $i \in [n], k \in [n^\beta], j \in [n]$
$$A^p_{i, k} = x^{A_{i, k}^{(l)}} \cdot y^{A_{i, k}^{(l + 1)}}$$
and
$$B^p_{k, l} = x^{B_{k, j}^{(l)}} \cdot y^{B_{k, j}^{(l + 1)}}$$
When computing the (standard) product $C^p = A^p \cdot B^p$, we will get for any $i, j \in [n]^2$ $$
C^p_{i, j} = \sum_{k \in [n^\beta]} x^{A_{i, k}^{(l)} + B_{k, j}^{(l)}} \cdot y^{A_{i, k}^{(l + 1)} + B_{k, j}^{(l + 1)}}
$$
So to filter out terms $A_{i, k}^{(l)} + B_{k, j}^{(l)}$ satisfying the first condition of \cref{lemma:filter}, we can compare the $y$-degrees of $C^p_{i, j}$ to $C^{(l+1)}_{i, j} + b$ for every offset $b \in \{-10, \dots, 10\}$ and keep the corresponding $x$-degrees. Now it might be the case that those terms don't satisfy the second condition, i. ~are such that $A_{i, k}^{*} + B^*_{k, j} \neq C^*_{i, j}$. This is why we construct for all $b \in \{-10, \dots, 10\}$ and $l \in \{h, \dots, 0\}$ the set $T_b^{(l)}$ of all terms such that the first condition of Lemma \ref{lemma:filter} holds, but not the second. We then subtract the erroneous terms selected by $T_b^{(l)}$ to keep only the terms of Lemma \ref{lemma:filter}. In order to efficiently compute the $T_b^{(l)}$ we will use previously computed $T_b^{(l+1)}$. To bound the size of the set  $T_b^{(l)}$ we will use the monotonicity of $B^{(l)}, C^{(l)}$ but we will also need the integer $p$ to be a prime number (see \cref{lemma:bound_Tb}).

Finally, a last detail to address is the running time for computing $C^p$.
The $x$ and $y$-degrees are bounded by
$O(n^{\alpha})$ and play a multiplicative factor in the computation of $C^p$.
We can improve this by replacing the $x$-degrees by $A_{i, k}^{(l)} - 2A_{i, k}^{(l+1)}$ and $B_{k, j}^{(l)} - 2B_{k, j}^{(l+1)}$ respectively. Then the $x$-degree becomes 0 or 1, and the computation of $C^p$ takes $\Tilde O(n^{\alpha} \cdot n^{\omega(\beta)})$ time.
\newline

\subsection{Algorithm}
We now describe the full algorithm in detail. Let $A$ and $B$ be matrices as in Theorem \ref{thm:fast_rect}, i.e.\ of dimensions $n \times n^\beta$ and $n^\beta \times n$ and such that $B$ is monotone with $O(n^\mu)$ bounded entries for some reals $\beta, \mu \geq 0$. Following the same reasoning as in \cite{chi2022faster}, we can assume that all entries of $A$ are non-negative and at most $O(n^\mu)$. As a consequence, the matrix $C = A \star B$ is row-monotone with non-negative entries at most $O(n^\mu)$.

Without loss of generality, we assume that $n$ is a power of 2. Let $\alpha \in (0, 1)$ be a constant parameter to be determined later. Pick uniformly at random a prime number $p$ in the range $[40n^\alpha, 80n^\alpha]$ and define the integer $h$ such that $2^{h-1} \leq p < 2^h$. Similarly as in \cite{chi2022faster}, we can make the following assumption (see \cref{lemma:ass}).

\begin{assumption}\label{ass:p/3}
For every $i, j$ either $(A_{i, j}~\mod~p)~<~p/3$ or $A_{i, j}~=~+\infty$. For every $i, j$ $(B_{i, j}~\mod~p)~<~p/3$ and each row of $B$ is non-decreasing.
\end{assumption}

The idea of the algorithm is to compute two matrices $C^*$ and $\Tilde{C}$ such that $C^*_{i, j} = \lfloor C_{i, j} / p \rfloor$ and $\Tilde{C}_{i, j} = C_{i, j} \mod p$ for each $i, j$. Then, to recover the original value $C_{i, j}$ simply compute $p \cdot C^*_{i, j} + \Tilde{C}_{i, j}$. We compute $C^*$ using a combinatorial approach, while we compute $\Tilde C$ iteratively, computing each bit at a time.

\paragraph{Compute the quotient matrix $\lfloor C /p \rfloor$} Define $A^*$ and $B^*$ as $A^*_{i, j} = \lfloor A_{i, j} / p \rfloor$ if $A_{i, j}$ is finite, otherwise $A^*_{i, j} = +\infty$, and $B^*_{i, j} = \lfloor B_{i, j} / p \rfloor$. Then, by Assumption \ref{ass:p/3}, the product $C^* = A^* \star B^*$ is such that if $C_{i, j}$ is finite then $C^*_{i, j} = \lfloor C_{i, j} / p \rfloor$.

Note that $B^*$ is row-monotone with entries bounded by $O(n^{\mu - \alpha})$. Thus in each row $k$ of $B^*$ we can define at most $O(n^{\mu - \alpha})$ intervals $[j_0, j_1] \subset [n]$ such that $B^*_{k, j_0 -1} \neq B^*_{k, j_0} = B^*_{k, j_0 + 1} = \dots = B^*_{k, j_1} \neq B^*_{k, j_1 + 1}$. To compute $C^*$ we first initialize each entry to $+\infty$. We then loop over each $i \in [n]$, each $k \in [n^\beta]$ and each interval $[j_0, j_1] \subset [n]$ as defined above for the $k$-th row of $B^*$ and update $C^*_{i, j} \gets \min \{C^*_{i, j}, A^*_{i, k} + B^*_{k, j_0}\}$ for each $j \in [j_0, j_1]$. This operation is correct since $B^*_{k, j} = B^*_{k, j_0}$ for every $j \in [j_0, j_1]$. Updating all elements $C^*_{i, j}$ for $j \in [j_0, j_1]$ can be done in logarithmic time using a segment tree. Hence the total running time to compute $C^*$ is the range of $i$ times the range of $k$ times the number of intervals in each row of $B^*$, i.e.\ $\Tilde{O}(n^{1 + \beta  + \mu - \alpha})$.

\paragraph{Compute the remainder matrix $(C \mod p)$} For every $0 \leq l \leq h$, construct $n \times n^\beta$ and $n^\beta \times n$ matrices $A^{(l)}$ and $B^{(l)}$ as $A^{(l)}_{i, j} = \left\lfloor \frac{A_{i, j} \mod p}{2^l} \right\rfloor$ if $A_{i, j}$ is finite, $A^{(l)}_{i, j} = +\infty$ otherwise and  $B^{(l)}_{i, j} = \left\lfloor \frac{B_{i, j} \mod p}{2^l} \right\rfloor$. We will iteratively construct an $n \times n$ matrix $C^{(l)}$ approximating $\left\lfloor \frac{C_{i, j} \mod p}{2^l} \right\rfloor$ if $C_{i, j}$ is finite. $C^{(l)}$ isn't defined directly but constructed such that it satisfies the following properties if $C_{i, j}$ is finite:
\begin{enumerate}[(1)]
    \item $\left\lfloor \frac{C_{i, j} \mod p \ - \ 2(2^l -1)}{2^l} \right\rfloor \leq C_{i, j}^{(l)} \leq \left\lfloor \frac{C_{i, j} \mod p \ + \ 2(2^l -1)}{2^l}  \right\rfloor$
    \item for $j_0 <j_1$, if $C^*_{i, j_0} = C^*_{i, j_1}$ then $C^{(l)}_{{i, j_0}}, \dots, C^{(l)}_{{i, j_1}}$ are monotonically non-decreasing
\end{enumerate}
Note that $C^{(l)}$ is not necessary equal to $A^{(l)} \star B^{(l)}$. We iteratively calculate matrix $C^{(l)}$ for $l = h, h-1, \dots, 0$ satisfying the above properties. Since $\left\lfloor \frac{C_{i, j} \mod p}{2^l} \right\rfloor$ can be seen as the approximation of $C_{i, j} \mod p$ up to the $l$-th bit, at each iteration we refine our approximation and  get in the end $\Tilde{C} = C^{(0)}$. To compute $C^{(l)}$ from $C^{(l+1)}$ we look for the minimum value of $A_{i, k}^{(l)} + B_{k, j}^{(l)}$ such that $k$ satisfies both conditions:
\begin{itemize}
    \item $A^{(l + 1)}_{i, k} + B^{(l + 1)}_{k, j} = C^{(l+1)}_{i, j} \ +\ b$ for some $b \in \{-10, \dots, 10\}$
    \item $A_{i, k}^{*} + B^*_{k, j} = C^*_{i, j}$
\end{itemize}
By \cref{lemma:filter} this ensures that $C^{(l)}$ satisfies both properties (1) and (2).

We will filter out terms according to the first condition and then remove the ones that don't satisfy the second condition. We explain later how the filtering according to the first condition is done and for now define the set of \textit{erroneous terms}, which are the terms satisfying the first condition but not the second.
For that, let us first make a series of observations.
All elements in $A^{(l)}, B^{(l)}, C^{(l)}$ are infinite or non-negative integers at most $O(n^{\alpha}/2^l)$. Furthermore, by property (2) of $C^{(l)}$, and since $B$ is row-monotone and elements of $B$ and $C$ are bounded by $O(n^\mu)$, every row of $B^{(l)}$ and $C^{(l)}$ is composed of $O(n^\mu/2^l)$ intervals, where all elements in each interval are equal. Also, each pair of rows of $B^{(l)}, C^{(l)}$ can be divided into $O(n^\mu/2^l)$ segments, where we define a segment as follow:
\begin{definition}
A segment $(i, k, [j_0, j_1])$ w.r.t $B^{(l)}$ and $C^{(l)}$ where $i, j_0, j_1 \in [n], k \in [n^\beta]$ and $j_0 \leq j_1$, satisfies that for all $j \in [j_0, j_1]$ $B^{(l)}_{k, j} = B^{(l)}_{k, j_0}$, $B^{*}_{k, j} = B^{*}_{k, j_0}$, and $C^{(l)}_{i, j} = C^{(l)}_{i, j_0}$, $C^{*}_{i, j} = C^{*}_{i, j_0}$.
\end{definition}

\noindent We can then define the set of erroneous terms $T_b^{(l)}$ for each offset $b \in \{-10, \dots, 10\}$ and every $l \in \{0, \dots, h\}$ as the set of segments $(i, k, [j_0, j_1])$
w.r.t  $B^{(l)}, C^{(l)}$ such that
$A_{i, k} < +\infty,\ A^{(l)}_{i, k} + B^{(l)}_{k, j_0} = C^{(l)}_{i, j_0} + b$ and
$A^{*}_{i, k} + B^{*}_{k, j_0} \neq C^{*}_{i, j_0}$.
We will show in Lemma \ref{lemma:bound_Tb} that the size of $T_b^{(l)}$ can be bounded by $\Tilde{O}(n^{1 + \beta + \mu -\alpha})$.

\paragraph{First iteration} The algorithm starts with $l = h$, so $A^{(l)}$, $B^{(l)}$, $C^{(l)}$ are zero matrices in the first iteration. $T_b^{(h)}$ is an empty set for $b \neq 0$ and $T_0^{(h)}$ is the set of segments $(i, k, [j_0, j_1])$ (w.r.t $B^{(h)}, C^{(h)}$) such that $A_{i,k} < +\infty$ and $A^{*}_{i, k} + B^{*}_{k, j_0} \neq C^{*}_{i, j_0}$. Since the number of segments in each pair of rows of $B^{(h)}, C^{(h)}$ is at most $O(n^\mu/p) = O(n^{\mu - \alpha})$ and since the number of pairs of rows of $B^{(h)}, C^{(h)}$ is $O(n^{1 + \beta})$, we can bound the size of $T_{b}^{(h)}$ for every $b \in \{-10, \dots, 10\}$ by $O(n^{1 + \beta + \mu - \alpha})$. Hence the first iteration does not take more than $O(n^{1 + \beta + \mu - \alpha})$ time.
\newline

Each following iteration of $l = h-1, \dots, 0$ consists in three phases: a polynomial matrix multiplication using $A^{(l)}$, $A^{(l+1)}$, $B^{(l)}$ and $B^{(l+1)}$ that allows to filter out candidates for $C^{(l)}$; a subtraction of the erroneous terms $T_b^{(l+1)}$; and finally the computation of $T_b^{(l)}$ using $T_b^{(l+1)}$. We describe the three phases for a fixed $l \in \{0, \dots, h-1\}$.

\paragraph{Polynomial matrix multiplication}
Construct two polynomial matrices $A^p$ and $B^p$ on variables $x, y$ as $A^p_{i, k} = 0$ if $A_{i, k}$ is infinite, otherwise:
$$A^p_{i, k} = x^{A^{(l)}_{i, k} - 2A^{(l + 1)}_{i, k}} \cdot y^{A^{(l+1)}_{i, k}}$$ and $$B^p_{k, j} = x^{B^{(l)}_{k, j} - 2B^{(l + 1)}_{k, j}} \cdot y^{B^{(l+1)}_{k, j}}$$
Compute the standard matrix multiplication $C^p = A^p \cdot B^p$. Since $A^{(l)}_{i, k} - 2A^{(l + 1)}_{i, k}$ and $B^{(l)}_{k, j} - 2B^{(l + 1)}_{k, j}$ are 0 or 1, the $x$-degree is bounded by 1. The $y$-degree is bounded by $O(p)= O(n^\alpha)$. Hence computing $C^p$ takes $\Tilde{O}(n^{\omega(\beta) + \alpha})$ time.

\paragraph{Filter candidates and subtract erroneous terms}
The previous computation of $C^p$ allows us to filter out candidate terms $A^{(l)}_{i, k}$ and $B^{(l)}_{k, j}$ that satisfy the first condition for $C^{(l)}_{i, j}$, i.e.\ $A^{(l + 1)}_{i, k} + B^{(l + 1)}_{k, j} = C^{(l+1)}_{i, j} + b$ for some $b \in \{-10, \dots, 10\}$.
Indeed we have that for every $i, j \in [n]^2$ either $C^p_{i, j} = 0$ or:
$$C^p_{i, j} = \sum_{k \in [n^\beta]} x^{A^{(l)}_{i, k} + B^{(l)}_{k, j}- 2A^{(l + 1)}_{i, k} - 2B^{(l + 1)}_{k, j}} \cdot y^{A_{i, k}^{(l+1)} + B_{k, j}^{(l+1)}}$$
If $C^p_{i, j} = 0$, set $C^{(l)}_{i, j} = +\infty$. Otherwise, build the following polynomial for each $b \in \{ -10, \dots, 10\}$:
$$
C^p_{i, j, b} (x) = \sum_{\substack{\lambda x^c \cdot y^d \text{ is a term in } C^p_{i, j} \\ d = C^{(l+1)}_{i, j} + b}} \lambda x^c
$$
This construction takes $\Tilde{O}(n^{1+\beta+\alpha})$ time for all $b \in \{-10 ,\dots,\\ 10\}$ and $i, j \in [n]^2$.
We then compute the polynomial corresponding to the erroneous terms:
$$
R^p_{i, j, b} (x) = \sum_{\substack{j \in [j_0, j_1] \\ (i, k, [j_0, j_1]) \in T_b^{(l+1)}}} x^{A^{(l)}_{i, k} + B^{(l)}_{k, j}- 2A^{(l + 1)}_{i, k} - 2B^{(l + 1)}_{k, j}}
$$
Since $B^{(l)}_{k, j} - 2B^{(l + 1)}_{k, j}$ is 0 or 1, there can be at most two different segments $(i, k, [j_0, j_1]) \in T_b^{(l+1)}$ corresponding to $B^{(l)}_{k, j}$, hence at most two different $R^p_{i, j, b} (x)$ per segment of $T_b^{(l+1)}$. In the end computing all $R_{i, j, b}^p (x)$ for all $b \in \{-10 ,\dots, 10\}, i, j \in [n]^2$ takes $\Tilde{O}(|T_b^{(l+1)}|)$ time.

Finally, let $s_{i, j, b}$ be the minimum degree of $x$ monomial of the difference $C^p_{i, j, b} (x) - R^p_{i, j, b} (x)$, and set $C^{(l)}_{i, j} = \min_{b \in \{-10, \dots, 10\}} \{s_{i, j, b} + 2(C^{(l+1)}_{i, j} + b)\}$.
This phase takes $\Tilde{O}(n^{1 + \beta + \alpha} + |T_b^{(l + 1)}|)$ time in total, which by Lemma \ref{lemma:bound_Tb} is $\Tilde{O}(n^{1 + \beta + \mu - \alpha})$.

\subparagraph{Computing $T_{b}^{(l)}$ from $T_{b}^{(l + 1)}$.}
By Lemma \ref{lemma:bound_Cl}, both $B^{(l)}_{k, j} - 2B^{(l + 1)}_{k, j}$ and $C^{(l)}_{i, j} - 2C^{(l + 1)}_{i, j}$ are between 0 and $O(1)$. So each segment w.r.t.\ $B^{(l+1)}$, $C^{(l+1)}$ can be split into at most $O(1)$ segments w.r.t.\ $B^{(l)}$, $C^{(l)}$. Furthermore, by \cref{lemma:bigcup}, we have $\bigcup_{b=-10}^{10} T_b^{(l)} \subset \bigcup_{b=-10}^{10} T_b^{(l + 1)}$. So to construct $T_{b}^{(l)}$, we need to look at each sub-segment of each segment in $\bigcup_{b=-10}^{10} T_b^{(l + 1)}$ and put it in the set $T_{b}^{(l)}$ it belongs to. Each segment in $T_b^{(l + 1)}$ can be split in at most $O(1)$ sub-segments and we can use binary search to find the splitting points. Hence the construction of $T_{b}^{(l)}$ for all $b \in \{-10, \dots, 10\}$,  takes $\Tilde{O}(|\bigcup_{b=-10}^{10} T_b^{(l + 1)} | ) = \max_{b \in \{-10, \dots, 10\}} \Tilde{O}(|T_b^{(l + 1)}|)$ time, which by Lemma \ref{lemma:bound_Tb} is $\Tilde{O}(n^{1 + \beta + \mu - \alpha})$.

\paragraph{Total running time} The expected running time of the algorithm is bounded by $\Tilde{O}(n^{1 + \beta + \mu - \alpha} + n^{\omega(\beta) + \alpha})$. Setting $\alpha = \frac{1 + \beta + \mu - \omega(\beta)}{2}$ we equalize both terms and get $\Tilde{O}(n^{\frac{1 + \beta + \mu + \omega(\beta)}{2}})$.

\subsection{Proof of correctness}\label{sec:algo_corr}

\begin{lemma}\label{lemma:ass}
The general computation of $A\star B$ where $B$ is row-monotone can be reduced to a constant number of computations of $A^i \star B^i$, where all of $A^i, B^i$ satisfy Assumption \ref{ass:p/3}.
\end{lemma}

\begin{proof}
The proof of analogous Lemma 3.4 in \cite{chi2022faster} applies verbatim, but we recall it anyway since it is useful to understand the proof of Lemma \ref{lemma:bound_Tb}.

We construct matrices $A', A'', A'''$ as follow:
\begin{itemize}
    \item if $(A_{i,j} \mod p) \in [0, p/3)$, let $A'_{i, j} = A_{i, j}$ ; $A''_{i, j} = A'''_{i, j} = +\infty$
    \item if $(A_{i,j} \mod p) \in [p/3, 2p/3)$, let $A''_{i, j} = A_{i, j}$ ; $A'_{i, j} = A'''_{i, j} = +\infty$
    \item if $(A_{i,j} \mod p) \in [2p/3, p)$, let $A'''_{i, j} = A_{i, j}$ ; $A'_{i, j} = A''_{i, j} = +\infty$
\end{itemize}
and row-monotone matrices $B', B'', B'''$ as follow:
\begin{itemize}
     \item if $(B_{i,j} \mod p)  \in [0, p/3)$, let $B'_{i, j} = B_{i, j}$ ; $B''_{i, j} = p \cdot \lfloor B_{i, j} / p \rfloor + \lceil p/3 \rceil$ ; $B'''_{i, j} = p \cdot \lfloor B_{i, j} / p \rfloor  + \lceil 2p / 3\rceil$
    \item if $(B_{i,j} \mod p) \in [p/3, 2p/3)$, let $B''_{i, j} = B_{i, j}$ ; $B'_{i, j} = p \cdot \lfloor B_{i, j} / p + 1 \rfloor$ ; $B'''_{i, j} = p \cdot \lfloor B_{i, j} / p \rfloor  + \lceil 2p / 3\rceil$
    \item if $(B_{i,j} \mod p) \in [2p/3, p)$, let $B'''_{i, j} = B_{i, j}$ ; $B'_{i, j} = p \cdot \lfloor B_{i, j} / p + 1 \rfloor$ ; $B''_{i, j} = p \cdot \lfloor B_{i, j} / p + 1 \rfloor  + \lceil p / 3\rceil$
\end{itemize}
Then each pair of $A^*$ and $B^*$, where $A^* \in \{A', A'' - \lceil p/3 \rceil, A''' - \lceil 2p/3 \rceil\}$ and $B^* \in \{B', B'' - \lceil p/3 \rceil, B''' - \lceil 2p/3 \rceil\}$, satisfies Assumption \ref{ass:p/3}. We compute the element-wise minimum $$C' = \min_{\substack{A^* \in \{A', A'', A'''\} \\ B^* \in \{B', B'', B'''\}}} \{ A^* \star B^*\}$$ Since elements in $A', A'', A'''$ become no smaller than the corresponding ones in $A$, and the same holds for $B', B'', B'''$, we have $C'_{i, j} \geq C_{i, j}$. But for the $k$ satisfying $C_{i, j} = A_{i, k} + B_{k, j}$, elements $A_{i, k}$ and $B_{k, j}$ must be in one of the 9 pairs, so $C'_{i, j} = C_{i, j}$.
\end{proof}

\begin{lemma}\label{lemma:bound_Tb}
The expected number of segments in $T_b^{(l)}$ is $\Tilde{O}(n^{1 + \beta + \mu - \alpha})$ for every $b \in \{-10, \dots, 10\}$ and every $l \in \{0, \dots, h\}$.
\end{lemma}

\begin{proof}
When $2^l > p/100$, the total number of segments is bounded by $\Tilde{O}(n^{1 + \beta + \mu - \alpha})$, so we assume next that $2^l < p /100$.

For any segment $(i, k, [j_0, j_1])$ w.r.t $B^{(l)}, C^{(l)}$, arbitrarily pick a $j \in [j_0, j_1]$ where $A_{i, k}$ is finite and $A_{i, k}^* + B^*_{k, j} \neq C^*_{i, j}$. By Assumption \ref{ass:p/3}, $(C_{i, j} \mod p) < 2p /3$. We have that $|A_{i, k} + B_{k, j} - C_{i, j}| \geq p/3$. Indeed, if $A^*_{i, k} + B^*_{k, j} \geq C_{i, j}^* + 1$ then

\begin{align*}
\frac{A_{i, k}}{p} + \frac{B_{k, j}}{p} &\geq \left\lfloor \frac{A_{i, k}}{p}\right\rfloor + \left\lfloor\frac{B_{k, j}}{p}\right\rfloor \geq \left\lfloor\frac{C_{i, j}}{p}\right\rfloor + 1 \\
&\geq \frac{C_{i, j}}{p} - \frac{2}{3} + 1 = \frac{C_{i, j}}{p} + \frac{1}{3}
\end{align*}
so $A_{i, k} + B_{k, j} \geq C_{i, j} + p /3$. Similarly if $A^*_{i, k} + B^*_{k, j} \leq C_{i, j}^* - 1$ then
\begin{align*}
\frac{A_{i, k}}{p} - \frac{1}{3} + \frac{B_{k, j}}{p} - \frac{1}{3} &\leq \left\lfloor \frac{A_{i, k}}{p}\right\rfloor + \left\lfloor\frac{B_{k, j}}{p}\right\rfloor \\
&\leq \left\lfloor\frac{C_{i, j}}{p}\right\rfloor - 1 \leq \frac{C_{i, j}}{p} - 1
\end{align*}
So we have $|A_{i, k} + B_{k, j} - C_{i, j}| \geq p/3$ in both cases.

We want to bound the probability that $(i, k, [j_0, j_1])$ appears in $T_b^{(l)}$, i.e.\ the probability that
$$
\left\lfloor \frac{A_{i, k} \mod p}{2^l} \right\rfloor + \left\lfloor \frac{B_{k, j} \mod p}{2^l} \right\rfloor = C^{(l)}_{i, j} + b
$$
holds, which is
$$
-4 \leq \frac{A_{i, k} \mod p}{2^l} + \frac{B_{k, j} \mod p}{2^l} - \frac{C_{i, j} \mod p}{2^l} - b \leq 4
$$
Let $C_{i, j} = A_{i, q} + B_{q, j}$. So if $(i, k, [j_0, j_1]) \in T_b^{(l)}$ then $(A_{i, k} + B_{k, j} - A_{i, q} - B_{q, j}) \mod p \in [2^l (b - 4), 2^l(b + 4)]$. This means that $A_{i, k} + B_{k, j} - A_{i, q} - B_{q, j}$ is congruent modulo $p$ to one of the $O(2^l)$ remainders. For each possible remainder $r \in [2^l(b -1, 2^l(b+4))]$, $(|b| \leq 10)$, we have
$$
|r| \leq 14 \cdot 2^l < p/6 \leq \frac{1}{2}|A_{i, k} + B_{k, j} - A_{i, q} - B_{q, j}|
$$
If $A_{i, k}, A_{i, q}$ are finite and $B_{k, j}, B_{q, j}$ are from the original $B$ (see Lemma \ref{lemma:ass}), $|A_{i, k} + B_{k, j} - A_{i, q} - B_{q, j} -r|$ is a positive number bounded by $O(n)$. The probability $P$ that $p \in [40n^\alpha, 80n^\alpha]$ divides $A_{i, k} + B_{k, j} - A_{i, q} - B_{q, j} -r$ is the quotient of the number of divisors of
$A_{i, k} + B_{k, j} - A_{i, q} - B_{q, j} -r$ over the number of primes in $[40n^\alpha, 80n^\alpha]$. There are at most $O(\log n)$ divisors of a $O(n)$ number. By the prime number Theorem \ccite{jameson2003prime}, there is at least $\Omega(n^\alpha/ \log n^\alpha)$ prime numbers in $[40n^\alpha, 80n^\alpha]$.  Hence $P = O(\frac{\log n \log n^\alpha}{n^\alpha}) = \Tilde{O}(n^{-\alpha})$.

In Lemma \ref{lemma:ass}, if $B_{k, j}, B_{q, j}$ are not from the original $B$ then they are set artificially to numbers congruent modulo $p$ to 0, $\lceil p/3 \rceil$ or $\lceil 2p/3 \rceil$. In that case, it still holds that $p$ divides $A_{i, k} + B_{k, j} - A_{i, q} - B_{q, j} -r$ with probability $\Tilde{O}(n^{-\alpha})$. To see this we can condition on different cases.
For example, if $B_{k, j}$ is congruent modulo $p$ to $\lceil p/3 \rceil$ and $B_{q, j}$ is from the original $B$, then we want that $p$ divides $A_{i, k} + \lceil p/3 \rceil - A_{i, q} - B_{q, j} -r$. Since 3 does not divide $p$, $3 \lceil p/3 \rceil$ is $p+1$ or $p+2$. So $p$ divides $3(A_{i, k}  - A_{i, q} - B_{q, j} -r) + 1$ or  $3(A_{i, k}  - A_{i, q} - B_{q, j} -r) + 2$. The probability that this is the case is $\Tilde{O}(n^{-\alpha})$ in both cases. Other cases of $B_{k, j}, B_{q, j}$ are similar. Summing conditional probabilities for all cases, we obtain that $p$ divides $A_{i, k} + B_{k, j} - A_{i, q} - B_{q, j} -r$ with probability $\Tilde{O}(n^{-\alpha})$.

Finally, there are $O(2^l)$ such possible remainders $r$, so the probability that $(i, k, [j_0, j_1])$ appears in $T_b^{(l)}$ is $\Tilde{O}(2^l n^{-\alpha})$. By linearity of expectation, since there are $O(\frac{n^{1 + \beta + \mu}}{2^l})$ segments $(i, k, [j_0, j_1])$ w.r.t.\ $B^{(l)}, C^{(l)}$, the expected number of segments in $T_{b}^{(l)}$ is $\Tilde{O}(n^{1 + \beta  + \mu - \alpha})$.
\end{proof}

\begin{lemma}\label{lemma:bound_Cl}
In each iteration $l = h, \dots, 0$ and for every $i, j \in [n]^2$, we have that $C_{i, j}^{(l)} - 2C_{i, j}^{(l+1)} \in [-7, 8]$.
\end{lemma}

\begin{proof}
The proof of analogous Lemma 3.5 in \cite{chi2022faster} applies verbatim.
\end{proof}

\begin{lemma}\label{lemma:bigcup}
For every $l=h-1, \dots, 0$, we have that \linebreak $\bigcup_{b=-10}^{10} T_b^{(l)} \subset \bigcup_{b=-10}^{10} T_b^{(l + 1)}$.
\end{lemma}

\begin{proof}
The proof of analogous Lemma 3.6 in \cite{chi2022faster} applies verbatim.
\end{proof}

\begin{lemma}
For every $l=h, \dots, 0$, if $A_{i, k} + B_{k, j} = C_{i, j}$, then there is some $b \in \{-10, \dots, 10\}$ such that $A_{i, k}^{(l)} + B_{k, j}^{(l)} = C_{i, j}^{(l)} + b$.
\end{lemma}

\begin{proof}
The proof of analogous Lemma 3.8 in \cite{chi2022faster} applies verbatim.
\end{proof}

\begin{lemma}\label{lemma:filter}
For every $l= h - 1, \dots, 0$ and $i, j \in [n]^2$, if we set $C_{i, j}^{(l)}$ to the minimum value of $A_{i, k}^{(l)} + B_{k, j}^{(l)}$ such that $k$ satisfies that:
\begin{itemize}
    \item $A^{(l + 1)}_{i, k} + B^{(l + 1)}_{k, j} = C^{(l+1)}_{i, j} + b$ for some $b \in \{-10, \dots, 10\}$
    \item $A_{i, k}^{*} + B^*_{k, j} = C^*_{i, j}$
\end{itemize}
then $C^{(l)}$ satisfies both properties (1) and (2).
\end{lemma}

\begin{proof}
The proof of correctness of Section 3.2.1 in \cite{chi2022faster} applies verbatim.
\end{proof}

\section{Applications}
\label{sec:applications}
In this section we list problems for which we can improve the bounds on the running time using \cref{thm:fast_rect}. We also improve running time for Unweighted Tree Edit Distance using the algorithm by \citet{chi2022faster} for Square Monotone Min-Plus Product. A summary of the improved bounds is given in \cref{fig:table_applications} but we detail the computations here.

\subsection{Single Source Replacement Paths}
\label{sec:SSRP}

In the SSRP problem, one is given an edge-weighted graph $G=(V, E, w)$ and a source $s \in V$ and has to find for all pairs $(v, e) \in V \times E$ the shortest path from $s$ to $v$ without using the edge $e$.
In \cite{polak}, \citeauthor{polak} use a Monotone Min-Plus Product algorithm to solve the \textbf{$M$-bounded SSRP} problem, which is the SSRP setting with edge-weights in $\{-M, \dots, M\}$
\footnote{As for Min-Plus Product, SSRP was shown in \cite{williams2010subcubic_focs, williams2010subcubic} to be sub-cubically equivalent to APSP. So under the APSP Hypothesis there is no truly sub-cubic time algorithm to solve SSRP in the general case.
\citet{polak} consider bounded weights to achieve a truly sub-cubic algorithm.}.

Their algorithm has a running time of (see \cite[Proof of Lemma 27]{polak}) $$\Tilde{O}(n^{\mu + \omega} + n^{\mu + \zeta + \omega(1-\zeta)} + n^{3 - 2\zeta} + n^{\varphi(1-\zeta, 1 + \mu)}),$$ where $M = n^\mu$ is the bound on the edge-weights, $\zeta\in[0, 1]$ is a parameter to optimize and $\varphi(\beta, \mu)$ is the function returning the smallest number such that the Monotone Min-Plus Product between matrices $A$ and $B$ of dimensions $n \times n^\beta$ and $n^\beta \times n$
with values of $B$ non-negative and at most $O(n^\mu)$ can be computed in $\Tilde O(n^{\varphi(\beta, \mu)})$ time. We recall that the interesting regime is when $0 \leq \mu \leq 3 - \omega$.
Using the bound on $\varphi(\beta, \mu)$ given in \cite{polak}, the running time is expressed as $\Tilde{O}(M^{\frac{5}{17-4\omega}} n^{\frac{36 - 7\omega}{17 - 4\omega}})$ using $\omega$ or as $\Tilde{O}(M^{0.8043}n^{2.4957})$ using known bounds for fast rectangular matrix multiplication.

\cref{thm:fast_rect} yields the tighter bound $\varphi(1-\zeta, 1 + \mu) \leq (3 + \mu - \zeta + \omega(1 - \zeta)) /2$. We can thus upper bound the running time of the algorithm by $\Tilde{O}(n^{\mu + \omega} + n^{\mu + \zeta + \omega(1-\zeta)} + n^{3 - 2\zeta} + n^{\frac{3 + \mu - \zeta + \omega(1 - \zeta)}{2}})$. Let's call $
A := \mu + \omega,\,
B := \mu + \zeta + \omega(1-\zeta),\,
C := 3 - 2\zeta \text{ and}\,
D := (3 + \mu - \zeta + \omega(1-\zeta))/2
$
the exponents of the different terms. We optimize $\zeta$ such that the exponent of $n$ equals $\min_{\zeta \in [0, 1]} \max \{A, B, C, D\}$ and will obtain running times of $\Tilde{O}(M^{\frac{2}{5 - \omega}} n^{\frac{9 - \omega}{5 - \omega}})$ using $\omega$ and $\Tilde{O}(M^{0.8825} n^{2.4466})$ using fast rectangular matrix multiplication. Remark that since $\mu \leq 3 - \omega$ the term $\Tilde O(n^A) = \Tilde O(Mn^\omega)$ is not dominant and thus can be omitted.\\

To express the running time as a function $\omega$, we bound $\omega(1 - \zeta) \leq (1 - \zeta) \cdot \omega + 2\zeta$ by implementing rectangular matrix multiplication by cutting rectangular matrices into square matrices and get:
\begin{align*}
    B &\leq \mu +\zeta  +  (1 - \zeta) \cdot \omega + 2\zeta \\
    &= \mu + \omega + \zeta \cdot (3 - \omega) &=: B' \\
    D &\leq (3 + \mu - \zeta + (1 - \zeta)\cdot \omega + 2\zeta)/2 \\
    &= (3 + \mu + \omega + \zeta \cdot (1 - \omega))/2 &=: D'
\end{align*}
Now equalizing $B', C$ and $D'$ we find $\zeta = \frac{3 - \mu - \omega}{5 - \omega}$ which is indeed in $[0, 1]$ for $0 \leq \mu \leq 3 - \omega$. Hence the dominant term is $B' = \frac{2\mu + 9-\omega}{5 -\omega}$. This yields an expected running time of $\Tilde{O}(M^{\frac{2}{5 - \omega}} n^{\frac{9 - \omega}{5 - \omega}})$. \\

To improve this bound we can use fast rectangular matrix multiplication and known bounds on $\omega(\beta)$.
Indeed, since the function $\omega(\beta)$ is convex in $\beta$, we can compute an upper bound on $\omega(\beta_0)$ and $\omega(\beta_1)$ for $\beta_0 < \beta_1$ and interpolate an upper bound on $\omega(\beta) \leq \frac{\omega(\beta_0)(\beta_1 - \beta) + \omega(\beta_1)(\beta - \beta_0)}{\beta_1 - \beta_0}$ for values $\beta \in [\beta_0, \beta_1]$.
Let's set $\zeta$ as a linear function of $\mu$, i.e.\ $\zeta = a + b \cdot \mu$ for some real numbers $a, b \neq 0$.
Then by optimizing $\max \{B, C, D\}$ with plugged in $\mu_0=0$ we obtain the optimal value for $\zeta_0 = a$.
When plugging in $\mu_1 = 3 - \omega$ we get the optimal value for $\zeta_1$ and compute $b = \frac{\zeta_1 - \zeta_0}{3 - \omega}$. Using the current best bound on fast matrix multiplication \cite{gall_rect} we get $a = 0.2767$ and $b=-0.4412$.
Set $\beta = 1 - \zeta$ and choose the bounds $\beta_0 = 1 - \zeta_0 = 1 - a = 0.7233$ and $\beta_1 = 1$. We get the following upper bound for $\zeta \in [0, 0.2767]$:
\begin{align*}
    \omega(1 - \zeta) &\leq \frac{\omega(\beta_0)(\beta_1 - (1 - \zeta)) + \omega(\beta_1)(1 - \zeta - \beta_0)}{\beta_1 - \beta_0} \\
    &= \frac{\omega(\beta_0)(a + b \cdot \mu) + \omega(\beta_1)(-b \cdot \mu)}{a} \\
    &= \omega(\beta_0) + \frac{b}{a} (\omega(\beta_0) - \omega(\beta_1)) \mu
\end{align*}
Using the values of $a$ and $b$ previously computed and the bounds on fast matrix multiplication \cite{gall_square} and fast rectangular matrix multiplication \cite{gall_rect}
, we obtain
$$\omega(1-\zeta) \leq 2.1698 + 0.3237 \mu$$
Finally, if we use this bound to optimize $\max \{B, C, D\}$,
we obtain the expected running time of the algorithm $\Tilde{O}(M^{0.8825}n^{2.4466})$.

\paragraph{Lower bound}
In \cite{polak}, \citeauthor{polak} have an interesting discussion about hardness of SSRP with negative weights as opposed to SSRP with positive weights. \citet{grandoni_william_ssrp} showed how to solve SSRP with positive weights in $\Tilde{O}(Mn^\omega)$ time, where $M$ is a bound on the weights. Subsequently this means that for weights in $\{0, 1\}$, we can solve SSRP in $\Tilde{O}(n^\omega)$ time. \citeauthor{polak} show that SSRP with weights in $\{-1, 0, 1\}$ seems harder than SSRP with weights in $\{0, 1\}$. They prove that if there exists a $T(n)$ time algorithm for SSRP in an $n$-vertex graphs with edge-weights in $\{-1, 0, 1\}$, then there exists an $O(T(n)\sqrt{n})$ time algorithm for the Bounded-Difference Min-Plus Product of $n \times n$ matrices. So if SSRP with $\{-1, 0, 1\}$ weights can be solved in $\Tilde{O}(n^2)$ time (if $\omega = 2$), then the Bounded-Difference Min-Plus Product could be solved in $\Tilde{O}(n^{2.5})$. The existence of the second algorithm seemed unlikely at the time of publication of \cite{polak}. However the new algorithm by \citet{chi2022faster} yields an $\Tilde {O}(n^{2.5})$ time algorithm if $\omega = 2$. Hence the above reasoning to lower bound the running time of SSRP with negative weights by $\Tilde{O}(n^2)$ (if $\omega = 2$) does not hold anymore.

\subsection{Batch Range Mode}

Let $a$ be an array of elements. A range mode query asks for the most frequent element in a given contiguous interval of $a$. In the \textbf{Batch Range Mode} problem, the array $a$ and all queries are given in advance, and the task is to compute all query answers.

The Batch Range Mode problem is solved by \citet{sandlund_rangemode} via a black box computation of a Monotone Min-Plus Product. Their deterministic algorithm runs in $\Tilde{O}(n^{ 1 + \tau} + n^{(1 - \tau) \cdot \varphi(1, \frac{\tau}{1 - \tau})})$ time (see \cite[Proof of Theorem 4]{polak}), where $\tau$ is a parameter in $[0, 1]$ and $\varphi(\beta, \mu)$ is the function returning the smallest number such that the Monotone Min-Plus Product between matrices $A$ and $B$ of dimensions $n\times n^\beta$ and $n^\beta \times n$ with values of $B$ non-negative and at most $O(n^\mu)$ can be computed in $\Tilde O(n^{\varphi(\beta, \mu)})$ time.

\citet{polak} already bound this running time by plugging in their algorithm for Monotone Min-Plus Product and obtained a running time $\Tilde O(n^\frac{21 + 2\omega}{15 + \omega})$. We further improve this bound by using Theorem \ref{thm:fast_rect}:
\begin{align*}
(1 - \tau) \cdot \varphi(1, \frac{\tau}{1 - \tau}) &\leq (1 - \tau) \cdot \frac{2 + \frac{\tau}{1 - \tau} + \omega}{2} \\
&= 1 + \frac{\omega}{2} - \frac{\tau}{2} (1 + \omega)\
\end{align*}
Equalizing this term to $1 + \tau$ we get $\tau = \frac{\omega}{\omega + 3}$ and the running time becomes $\Tilde O(n^{1 + \frac{\omega}{\omega + 3}}) = \Tilde O(n^{\frac{3 + 2\omega}{3 + \omega}})$. With current best bound on fast matrix multiplication \cite{gall_square} this is $\Tilde{O}(n^{1.4416})$.

\subsection{$k$-Dyck Edit Distance}

The Dyck Edit Distance of a sequence $S$ of parenthesis (of various types) is the smallest number of edit operations (insertions, deletions, and substitutions) needed to transform $S$ into a sequence of balanced opening and closing parenthesis. \citet{dyck} study the \textbf{$k$-Dyck Edit Distance} problem in which the input is an $n$-length sequence of parenthesis $S$ and a positive integer $k$ and the task is to compute the Dyck Edit Distance of $S$ if it is at most $k$, otherwise to return $k+1$.

\citeauthor{dyck} show how to solve it in time $\Tilde O(n + k^2 \cdot {\psi(k, \sqrt{k})})$ (see \cite[Theorem 1.1]{dyck}), where $\psi(a, b)$ is the running time to compute the Min-Plus Product between two bounded-difference matrices of dimensions $a \times b$ and $b \times a$.
To bound $\psi(a, b)$, \citeauthor{dyck} use the algorithm for Bounded-Difference Min-Plus Product in \citet{rna_led_osg} and get a running time of $\Tilde O(n+k^{4.7820})$.

Our new result of \cref{thm:fast_rect} yields a tighter bound of $\psi(n, n^\beta) \leq \Tilde O(n^\frac{2 + \beta + \omega(\beta)}{2})$. Hence the running time improves to $\Tilde O(n + k^{\frac{5}{2} + \omega(1/2)})$, which is $\Tilde O(n + k^{4.5442})$ with the current best bound on fast rectangular matrix multiplication \cite{gall_rect}. Actually if $k \geq \sqrt{n}$, \citeauthor{dyck} show a faster algorithm running in time $\Tilde O(\psi(n, k))$ (see \cite[Section 4]{dyck}), which we can directly bound to $\Tilde O(n^{\frac{2 + \log_n k + \omega(\log_n k)}{2}}) = \Tilde O(n \sqrt{k n^{\omega(\log_n k)}})$.

\subsection{2-approximation APSP}

The All Pairs Shortest Path (APSP) problem asks for a given graph $G = (V, E)$ the shortest path between all pairs of vertices. \citet{apsp_approx} consider a \textbf{2-approximation to APSP} for undirected unweighted graphs, which is a mapping $\hat d: V \times V \rightarrow \mathbb{N}$  such that $d_{OPT}(u, v) \leq \hat d(u, v) + 2$ for every vertices $u$ and $v$, where $d_{OPT}(u, v)$ is the distance from $u$ to $v$.

The 2-approximation to APSP is computed by \citeauthor{apsp_approx} by using Bounded-Difference Min-Plus Product as a black-box. When $n = |V|$, the running time of their algorithm is $\Tilde O(n^2 t^{1/2} + \psi(n, n/t))$ (see \cite[Theorem 11]{apsp_approx}), where $t \geq 1$ is a parameter and $\psi(a, b)$ is the running time to compute the Min-Plus Product between two bounded-difference matrices of dimensions $a \times b$ and $b \times a$. \citeauthor{apsp_approx} use the algorithm for Bounded-Difference Min-Plus Product in \citet{rna_led_osg} and get a running time of $\Tilde O(n^{2.2867})$. With \cref{thm:fast_rect} we have an improved upper bound on $\psi$ and can thus compute a 2-approximation of APSP in $\Tilde O(n^2 t^{1/2} + n^{\frac{2 + \log_n(n/t) + \omega(\log_n(n/t))}{2}})$ time. By setting $t = n^{0.5185}$, the running time becomes $\Tilde O(n^{2.2593})$ using current best bounds on fast rectangular matrix multiplication \cite{gall_rect}.

\subsection{Unweighted Tree Edit Distance}

Given an alphabet $\Sigma$ and a rooted ordered tree with node labels in $\Sigma$, we consider two types of operations: relabeling a node to another symbol of $\Sigma$ and deleting a node $v$ such that the children of $v$ become children of the parent of $v$ with the same ordering.
The \textbf{Unweighted Tree Edit Distance} between two rooted ordered trees $T_1$ and $T_2$ is the minimum number of operations to perform on $T_1$ and $T_2$ so that they become identical
\footnote{In the weighted case, the cost of deletions and relabeling is a function of the symbol on the nodes. \citet{weighted_ted_soda, weighted_ted} show that the Weighted Tree Edit Distance does not admit any truly subcubic algorithm under the APSP Hypothesis, if $T_1$ and $T_2$ have both $n$ nodes and $|\Sigma|=\Theta(n)$.
}.

In \cite{treeED}, \citeauthor{treeED} shows the first truly sub-cubic algorithm to solve the Unweighted Tree Edit Distance. For two trees of size $n$ and $m$, the simplified expression of the running time is $\Tilde O(n \cdot m^\frac{3\alpha -1}{\alpha +1})$ (see \cref{app:ted}), where $\alpha$ is the exponent of the Bounded-Difference Min-Plus Product between square matrices. Using the algorithm for Bounded-Difference Min-Plus Product of \citet{rna_led_osg}, the running time can be bounded by $\Tilde O(n \cdot m^{1.9541})$ time, which is subcubic if $m=O(n)$. We remark here that the running time $\Tilde O(n \cdot m^{1.9546})$ announced in \cite{treeED} is slightly worse due to a numerical error.

Since a $n \times n$ bounded-difference matrix can be transformed into a row-monotone matrix with non-negative entries bounded by $O(n)$, the work of \citet{chi2022faster} allows us to get a tighter bound on $\alpha \leq \frac{3 + \omega}{2}$. We can thus bound the running time by $\Tilde O(n \cdot m^\frac{3\omega + 7}{\omega + 5})$. With the current best bound on fast matrix multiplication \cite{gall_square}, this is bounded by $\Tilde O(n \cdot m^{1.9149})$.

\section*{Acknowledgment}
I would like to thank Adam Polak for introducing the topic to me and for instructive guidance.

redpajama_set_name: RedPajamaArXiv


To service leak call us and we will do it for a fixed rate with a one-year certify contract in Hounslow TW8.
It is not the best idea to repair a leak on your own if you do not have the basic competence low pressure is most of course a sign of a leak, to put right a leak in Hounslow TW8 contact us and we will send a trained plumbing expert for a quick and satisfactory patch up Due to a very high water pressure inside the upvc pipe cracks may be formed which ultimately may lead to a serious leakage. How much does it cost to put right a leak in the main steel pipe of the apartment by a professional plumbing company in Hounslow TW8? If you would like to put in place a tap or mend a leak in your home in Hounslow TW8, you can call our professional plumbing company and get help right away.


text:
Court of Appeal rules on enforcement of exclusive jurisdiction agreement against insurers acting by way of subrogation
In an important case on the enforcement of exclusive jurisdiction clauses, the Court of Appeal has rejected a challenge to the exclusive jurisdiction of the English court made by insurers of an Italian airline who had brought proceedings in Italy against the aircraft manufacturer -Airbus. In response to the Italian proceedings Airbus commenced proceedings in England seeking declaratory relief to give effect to the exclusive jurisdiction clause against. The insurers of the airline challenged the jurisdiction of the English court. The insurers having been unsuccessful at first instance appealed. The Court of Appeal in dismissing the appeal has provided an instructive exposition on: (i) the approach taken to construing jurisdiction agreements where there are different agreements with different jurisdiction clauses; (ii) the applicable test to determine jurisdiction challenges where there are issues of fact in dispute and where there are questions of law in relation to which the court has all the relevant materials to make a final decision; and (iii) the power of the court to grant declaratory relief in support of an equitable obligation equivalent to a contractual right.
On this last point the Court of Appeal has made clear that where insurers are exercising rights derived by subrogation or assignment the English court has the power to make a declaration against the insurers. In particular, the court held that: (i) insurers exercising rights of subrogation to make a non-contractual claim were bound by an English arbitration or jurisdiction clause to the same extent as an insured would have been; (ii) the commencement and pursuit of such proceedings by insurers was a breach of an equivalent equitable obligation equivalent to a contractual right not commence or pursue proceedings contrary to the terms of the arbitration or jurisdiction agreement; and (iii) the court would give effect to that equitable obligation by granting appropriate declaratory relief. The Court of Appeal expressly approved the first instance decision of Mr Justice Colman in West Tankers [2005] EWHC 454 on this point.
The Court's judgment can be found here and is likely to be of interest to practitioners in cross-border disputes and in the insurance market.
Airbus was represented by Akhil Shah QC, instructed by Kathryn Ward and Sophie Brophy of DLA Piper.
'A wonder set'

redpajama_set_name: RedPajamaCommonCrawl


Tags: rail, arm, Cheap rail, High Quality arm.
Features: Photo studio with foldable design which is unfolding a whole new level of possibilities in smartphone photography. It enables everyone to take awesome, studio-quality pictures with a smartphone using a simple setup. Magnetic structure.


Found photographs of anonymous groups of males. A woman isolates each face then stares into it until women's intuition brings about a certainty as to the man's name. I write the name on in permanent ink. If you would like to try for yourself, don't look too closely at the image above but scroll through the faces below.
Women's Intuition (small boys) was made with the participation of female faculty members and students from Denison University, and Nova Scotia College of Art and Design.


Work has really been interfering with my crafting life lately and, as it's also classes week for me, crafting time has been in short supply. I got to it straight after work last night though to make a gift and card for a friend. She's a crafter too and I always make her a card then give it to her unwritten in so she has the choice of keeping it or using it for someone else. It's a bit of a joke between us.
For inspiration, I turned to one of my favourite challenge sites, Just Add Ink, where there is a sketch this week.
I also got out one of the Sale-abration items I received that I hadn't used before, Avant Garden. Now that I've used it, I'm only sorry it has sat unopened on my desk for so long!
I wasn't quite sure what to make of the horizontal line in the sketch but I've made it the place where the stamping stops.
I've added some touches of gold Wink of Stella to the stamens but it is hard to capture in the photo.
I also made wee chocolate box, just the right size for six of those delicious Lindor chocolate balls. The dimensions for the box I cased from Pootles' triple creme egg window box here.
Then I had a problem because I wanted to give her some glue and dimensionals as well. It turns out that dimensionals are packaged in a very annoying sized package that means they will not fit into things made on a gift bag punch board, so I had to custom make a gift bag to fit the glue, dimensionals and the chocolate box.
It was a lot to fit into an after-work-but-before-bed session but I'm happy with the results. And so, I think, was my friend!
P.S. I did tidy up the ends of the pink ribbon once everything was safely stowed inside the bag.
I cut the ribbons generously because I'm pretty sure they'll end up in her stash drawer.
Other: Natural trim ribbon, gold Wink of Stella, gold metallic shapes, Early Espresso marker to outline the sentiment, dimensionals.
Such a gorgeous collection Jan. I still haven't inked up this set either, but after seeing this l know what l'm doing tomorrow...love it!
Thanks for sharing at Just Add Ink.
What a beautiful set you created with this stamp!! I love the colors you used!!
I love your take on the sketch, and the gorgeous soft colours you've used, Jan. Such a beautiful gift set for your friend. Thanks for joining us at Just Add Ink this week.
So very pretty, Jan & a lovely gift for your friend. I'm sure she'll love it. Glad you managed to find the time to play along with us at JAI.


Kitchen appliances are constantly evolving, their design and feature change almost all the time and while there are many tech lovers who are thrilled about this, most of us would want to have a classic and why not, retro-inspired appliances. Retro is a timeless trend and it will always be classy. If you are planning to buy a retro-inspired appliance, you should check out these 3 practical and beautiful models.
Smeg is an Italian company who has been making appliances since the year 1948, so if you are looking for a modern refrigerator that has a retro design, you should take a look at what they have to offer. We like the retro fridges because they come in a variety of bold and bright colors and they have that timeless and classy look that most of us love. The exterior design of Smeg fridges is simply very well put together and it can complement any type of kitchen, whether it is modern or retro, you'll find a place for your colorful Smeg fridge. These refrigerators are also highly practical because they come with plenty of storage space and a freezer compartment to store your favorite icecream. If you don't have a lot of space in the kitchen you can also opt for a mini version of the Smeg fridge.
If you are planning to use the retro design as an inspiration for designing your kitchen, note that you can easily create a vintage-looking kitchen with the right accessories and mostly important with carefully chosen appliances. Here's another vintage-looking appliances that benefits from many impressive features. The Big Chill Jadite Green Retro Microwave features an elegant and stylish design. What makes this microwave so popular is the fact that you can combine the chrome and green trimming with green, red, blue or other color of your choice. If you take a look at some microwave reviews, you will be able to compare this microwave with the best rated microwave ovens of the moment. You will see that this retro microwave offers the same functions as most of the modern microwave ovens, only the exterior design is different.
A good-quality dishwasher is extremely useful because let's face it, who likes to spend hours in the kitchen washing dishes? Nowadays, you can find a wide variety of dishwasher models on the market. If you take a look at some dishwasher reviews, you will see that the latest models come with a lot of amazing new features. If you can't decide between a retro dishwasher and a modern one, consider mixing the modern dish-washing technology with the retro design and you're set. The Big chill dishwashers are energy efficient, meaning that they operate on less water and energy, thus helping you to make some savings at the end of the month. Another great advantage of owning a Big Chill dishwasher is that you can choose from a variety of colors, so you can either make the dishwasher blend seemingly with other appliances or furniture pieces or opt for a dishwasher in a bold color such as orange and red to add a touch of playfulness to your kitchen space.


text:
The Law Offices of C. Lee Hewitt
Tips for communicating with a co-parent to reduce stress
Can you minimize the impact of divorce on your child?
Addressing feelings of helplessness in an abusive relationship
Three common misconceptions about financial power of attorney
Divorce & Legal Separation
Spousal & Child Support
Paternity Cases: Support & Custody
Advance Health Care Directives & Powers of Attorney
Estate Planning: Wills & Trusts
Probate Litigation & Estate Disputes
How to reach an agreement on property division during a divorce
On behalf of The Law Offices of C. Lee Hewitt on Friday, August 3, 2018.
The decision to get a divorce is usually not easy. You pledged to spend your life together, and now you must decide who gets the TV and the treadmill. Worrying about who gets what may seem trivial when you are going through such an emotionally traumatic experience.
Continue reading How to reach an agreement on property division during a divorce...
39510 Paseo Padre Pkwy
The Law Offices of C. Lee Hewitt represents people in Fremont and throughout the East Bay area of California, including Hayward, Milpitas, Newark, San Jose, Palo Alto, Pleasanton, Castro Valley, Livermore, Mountain View, Menlo Park, Martinez, Silicon Valley and all cities within Alameda County, CA.
© 2020 by The Law Offices of C. Lee Hewitt. All rights reserved. Disclaimer


Jenny has been a hairdresser for twenty four years and absolutely loves her job! She especially loves the challenge of cutting hair precisely and creatively so the hair moves and falls expertly around the face and head. Her clients know they have an expert haircut every time they leave the salon because so many people ask them "who does your hair?" Jenny's attention to detail and creative inspiration bring her clients back again and again. Jenny is warm hearted and fun, making the salon a lively and comfortable place for clients and stylists to interact. For her, being a hairdresser goes deeper than just a hairstyle. She believes that her purpose and greatest gift is to pamper people by making them feel happy, loved, and beautiful.


text:
Coca-Cola says it has invested over $5m to tackle plastic pollution across Africa
On Jun 6, 2019
The Coca-Cola Company says it has invested more than $5 million to tackle plastic pollution across the African continent. Plastic pollution has been identified as one of the major threats to the global environment, and in response of which some countries are banning single use plastic items and products.
In a press release copied to ghanabusinessnews.com, Coca-Cola says it is on track to spend a third of its $38 million pledge before the end of 2019. The company in December 2018 committed to invest $38 million over three years to stimulate polyethylene terephthalate (PET) plastic collection and recycling in Southern and East Africa as part of its local effort to achieving a global World Without Waste vision.
"World Without Waste is an ambitious global Coca-Cola goal to help collect and recycle a bottle or can for every one it sells by 2030," the release said.
The company, according to the release has since the beginning of this year, together with its bottling partners has invested $5.125 million to boost recycling industries across eight countries.
"PET collection and recycling rates are steadily increasing. As a percentage of the PET plastic it sells, the Coca-Cola system in Southern and Eastern Africa is forecasted to close 2019 with an average collection and recycling rate of 80 per cent, led by South Africa at 114 per cent," it indicated.
Coca-Cola notes that PET recycling industries have been established in Kenya, Mozambique, Namibia, South Africa, Tanzania, Uganda, Zambia and Zimbabwe on the back of industry collaboration and funding kick-started by the company and its main bottling partner across Africa, Coca-Cola Beverages Africa.
World Without Waste is a Coca-Cola goal to help collect and recycle a bottle or can for every one it sells by 2030. Additionally, the Coca-Cola Company will create packaging that contains at least 50 per cent recycled material by 2030, meaning less virgin material will be used. The company will also continue pursuing the goal to make all consumer packaging 100 per cent recyclable by 2025, it added.
By Emmanuel K. Dogbevi
Copyright ©2019 by Creative Imaginations Publicity
All rights reserved. This article or any portion thereof may not be reproduced or used in any manner whatsoever without the express written permission of the publisher except for the use of brief quotations in reviews.
29 players in camp, as Black Stars now have full house
As the rains come, flooding endangers school children in Africa


text:
The Koide Formula
There are three charged leptons: the electron, the muon and the tau. Let and be their masses. Then the Koide formula says
There's no known reason for this formula to be true! But if you plug in the experimentally measured values of the electron, muon and tau masses, it's accurate within the current experimental error bars:
Is this significant or just a coincidence? Will it fall apart when we measure the masses more accurately? Nobody knows.
Here's something fun, though:
Puzzle. Show that no matter what the electron, muon and tau masses might be—that is, any positive numbers whatsoever—we must have
For some reason this ratio turns out to be almost exactly halfway between the lower bound and upper bound!
Koide came up with his formula in 1982 before the tau's mass was measured very accurately. At the time, using the observed electron and muon masses, his formula predicted the tau's mass was
= 1776.97 MeV/c2
while the observed mass was
= 1784.2 ± 3.2 MeV/c2
Not very good.
In 1992 the tau's mass was measured much more accurately and found to be
= 1776.99 ± 0.28 MeV/c2
Much better!
Koide has some more recent thoughts about his formula:
• Yoshio Koide, What physics does the charged lepton mass relation tell us?, 2018.
He points out how difficult it is to explain a formula like this, given how masses depend on an energy scale in quantum field theory.
This entry was posted on Sunday, April 4th, 2021 at 3:55 am and is filed under physics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.
46 Responses to The Koide Formula
Bartosz Milewski says:
This reminds me of the Eddington's obsession with the number 137 and the Titius–Bode law of planetary distances.
Well, Eddington started out writing a long explanation of why the reciprocal of the fine structure constant was 136. Then when it measured to be closer to 137 he said he'd left something out. But it's even closer to 137.036.
When I die my first question to the Devil will be: What is the meaning of the fine structure constant? — Wolfgang Pauli
The big question is whether there's any explanation at all for the 25 dimensionless constants in the Standard Model. But most of what people write about this is nonsense. A nontrivial relation between them, like the Kohde formula, would be an enormous clue… if it were true.
There are lots of interesting relations between masses of hadrons, but these are very different: there are underlying reasons for these. Around 1962 Gell–Mann used one to predict the mass of the Ω:
• Gell-Mann–Okubo mass formula.
Those were the good old days!
linasv says:
Ever look into harmonic maps? I've always planned to dig into them more deeply, never have, but got the general impression that they're more-or-less the same thing as the sigma model in low-energy nucleon physics, of which the chiral model is a special case. I'm throwing this out because there's a natural "square root of the laplacian" appearing there, which, with a lot of gymnastics and hand-waving, might be thought of as the the "square root of the mass". That is to say, one could argue that both the numerator and the denominator of the Koide formula might appear "naturally" in this setting. I wish I could clone myself, so that I had time to pursue this idea. Alas.
Yes, the differential equation for harmonic maps underlies so-called "nonlinear sigma-models".
There must be a lot of work trying to explain the Kohde model, but I haven't read most of it, and obviously most of this work must be wrong.
(My PhD thesis was on non-linear sigma models.) I guess I'm trying to say that "harmonic maps" is a chapter you might find in a book on Riemannian geometry. Geometry is the kind of place where one finds formulas involving integers and fractions that arise from first principles. Yet, on the other hand, the solitons that appear in non-linear sigma models are reasonable models of the low-energy properties of baryons. As such, the solitons have to be interpreted as spin-1/2 (exactly how is mysterious, at least to me). Well, your leptons are spin-1/2. The probably-just-plain-wrong idea I'm proposing is that perhaps leptons can be interpreted as solitonic excitations. Have to pull a Dirac operator out of that mess. But insofar as that's a geometric claim, a fiddling with geometry, it strikes me as plausible that something like the Koide formula could fall out. Yes, I've sketched an imaginary incoherent fairy-tale to bridge a chasm that is too wide. But still, I find it entertaining, Perhaps because I'm infatuated with the geometry of Dirac operators. I'll leave it at that.
4 April, 2021 at 4:26 pm
Okay, sorry, so I don't have to explain harmonic maps vs. nonlinear sigma-models to you! I guess the term "harmonic map" is mainly used to mean a map from a Riemannian manifold (space) to another Riemannian manifold (the target manifold) which is a critical point of a certain action, while nonlinear sigma-models also study maps from a Lorentzian manifold (spacetime) to a Riemannian manifold (the target manifold) which are critical points of the analogous action. So the math literature on harmonic maps would probably mainly help with the static behavior of nonlinear sigma-models.
If I were trying to dream up a soliton-based explanation of lepton masses, I'd start by reading this article and a bunch of the references:
• nLab, Skyrmion.
There's been a lot of interesting work recently, which I haven't followed at all!
Obviously, using telepathy to communicate ideas isn't working out! My PhD was actually about coupling free quarks to Skyrmions. At that time, I did not know that a special case of Riemannian manifolds are spin manifolds, where the frame bundle vierbeins can be arranged to allow a consistent spin bundle, and thence Dirac operators. What I don't understand is what happens if one throws spin manifolds into harmonic maps and stir the pot. Even simple questions: given a Skyrmion as a background field, can I consistently glue spin structures together between the spacetime manifold and the target chiral manifold? If this gluing can be accomplished, is there a corresponding bound state of the Dirac field (in the target space), non-vanishing where-ever the Skyrmion field is non-vanishing? I am aware that Dan Freed at UTexas has done work on this (and that Karen Uhlenbeck sits down the hall) but I'm not familiar with it.
Here's where the geometry comes in: The target-space of a sigma model can be any symmetric space. This provides a rich playground of groups to play with, and all sorts of invariants necessarily precipitate. (For example, the chiral anomaly is more-or-less the odd-parity part of the Cartan involution, from what I can tell.) Again: what happens if spin structures are thrown into this mix?
The Skyrmion has a mass that is more-or-less inversely proportional to its radius, and "magically" has the proton mass, given the proton radius (its off by about 20%). If one were to write down a spinor field (that lives on the target manifold, not the spacetime manifold), bound to the Skyrmion field, is it's effective mass also the same? I haven't a clue. What would excitations of this field look like? Are they bound to the Skyrmion? (Are they "confined"?) I assume that one can consistently glue a spinor in the target manifold to a spinor field on the spacetime manifold, but what does this look like and what does it imply? I dunno, I'm not convinced that the questions I asked make sense.
My general impression is that there is very little work on the interplay of spin structures and harmonic-maps aka chiral-models. Obviously, I forgot to mention leptons up above, so let me do so now: by convention, the skyrmion is interpreted as a nucleon, so the associated isospin/flavor is interpreted as up/down, instead of electron/muon. But in a more general framework, might there be an instanton instead of a skyrmion? Could that instanton involve lepton fields? Could some prestidigitation produce the Koide formula? This is the idle daydream I wanted to communicate. And yes, as I re-read what I just wrote, it seems dubious.
This took me under half-an-hour to type up; yet if I were to follow my own nose and investigate the possibilities I'm proposing, I know it would take me months stretching into years to gain a more refined understanding. Every time I start to think I am a wunderkind with pencil-n-paper calculations, I find a sign error that takes days to resolve. Either that, or scrambling to reference works to validate notation and identities, followed by pleasant distractions found in those references. I imagine its the same for everyone.
Phillip Helbig says:
• Louis J. Dubé, A reminder of the powers of π, Physics Today.
Can't read it? Due to the COVID-19 pandemic, Physics Today has made its entire archive publicly accessible to those who register.
Toby Bartels says:
I have a feeling that this article was originally published within 3 days of a whole number of years ago.
Nope, 15 May.
Ah, too bad. Now that I look again, I see a faint grey '01 November'. Perhaps it was submitted on April 1. Anyway, the comments are illuminating.
The Physics Today paper is 1 November, but it talks about a Physical Review paper from decades ago, which appeared on 15 May.
I don't think that it was a joke.
I'm sure that the 1951 letter by Lenz was serious. But the 2017 reminder implies (although without outright stating so) that the coincidence still holds for the many more digits that we now have (or at least had in 2017), when it actually doesn't hold for any additional digits (as noted in the online comments).
It does note that it now holds only to a good approximation, whereas in 1951 it held exactly (i.e. within the experimental accuracy). One could also take it to mean that the values for the masses were already pretty good in 1951. (Compare to the fine-structure constant, which for a time was believed to be exactly 1/136, or 1/137.)
Interesting! I rediscovered the formula
myself as a kid, by fiddling around on a calculator. But I didn't take it very seriously, because it was already clear to everyone that the proton mass is a rather complicated spinoff of QCD, not something there should be a simple formula for.
In their magnum opus, Barrow and Tipler calculate whether such numerical coincidences are surprising or not, based on how many constants, which powers, and so on one has to select from.
The age of the universe in Planck units is , which is the square root of the alleged factor of over-prediction of the value of the cosmological constant. Barrow and Shaw wrote some papers, which I don't begin to understand, connecting the two quantities.
Sadly, John is no longer with us (and Tipler has gone off the deep end).
mitchellporter says:
The category theorist Marni Sheppeard could have contributed a lot to this discussion, since she worked for years on explaining the Koide formula, but she was found dead a week and a half ago. It's a terrible thing that we're having this discussion without her.
In particular she worked with Carl Brannen, who in 2006 found a trigonometric expression for Koide's formula which gives the physical masses, for an angle of exactly 2/9 radians. The precision of it was enough to catch the attention of Koide himself (arXiv:0706.2534, eqns 3.9-3.10)… Brannen and Sheppeard tried to explain it in the context of circulant (cyclically symmetrical) mass matrices, a form pioneered by Harrison and Scott (hep-ph/0203209).
nad says:
4 April, 2021 at 12:32 pm
Sad to hear this. Mountaineering is unfortunately a rather dangerous sport and very sadly hits also experienced mountaineers (see e.g. also https://en.wikipedia.org/wiki/Oded_Schramm).
I have never met her, but saw that she commented on and off to the n-category café. I asked John, when I met him in Oxford, whether he knew about her whereabouts, but he didn't knew much. (I think she spend also some time in Oxford).
Did you know her?
I first met Marni Sheppeard when she was working with Louis Crane on what came to be called the Crane–Sheppeard model. I later spent a long time developing the math of this model, which involve representations of something called the Poincaré 2-group. My student Derek Wise, Laurent Freidel and his student Aristide Baratin and I developed the foundations of this sort of representation theory in a book called Infinite-Dimensional Representations of 2-Groups. By the end we were too exhausted to develop the model, but recently there's been some new work on it:
• Seth K. Asante, Bianca Dittrich, Florian Girelli, Aldo Riello and Panagiotis Tsimiklis, Quantum geometry from higher gauge theory.
I later was a reader for Marni Sheppeard's PhD thesis, which unfortunately was a garbled mix of smidgens of topos theory and twistor theory, nothing that made sense.
Once she got lost for days in some mountains in New Zealand and Louis Crane played some role in rescuing her—I forget exactly what, maybe he just noticed that she was missing. So her death, while tragic, was foreshadowed.
David Chester says:
What I find remarkable about Marni's thesis was that she mentioned the utility of associahedra for QCD. This was vindicated, as Melia's 2013 work on quark color decomposition used associahedra. Also, Nima Arkani-Hamed et al. by 2017 showed that associahedra give tree amplitudes of biadjoint scalar theory, which is known to double copy to Yang-Mills theory. Therefore, it seems that Marni's thesis had some good moments.
https://physicstoday.scitation.org/doi/10.1063/1.2811237
The classic paper on particle-physics numerology: https://physicsgg.files.wordpress.com/2017/04/on-the-quantum-theory-of-the-absolute-zero-of-temperature.pdf
Johan Swanljung says:
Nitpicking, but if the masses are all positive (in the puzzle), the ratio must be strictly less than 1.
That's right. What I wrote is also correct.
allenknutson says:
These are the running masses (when surrounded by virtual particles), not the bare masses (which I presume need renormalization), right? Is this the sort of relation that would continue to hold at high energies?
The Wikipedia page has a comment about this:
https://en.wikipedia.org/wiki/Koide_formula#Running_of_particle_masses
Yes, in the current 'top-down' thinking about particle physics, where the fundamental physics appears at high energies and gets tweaked by the renormalization group as we descend to lower energies, it's very hard to understand why an exact relation like the Koide formula would hold at low energies. I added a tiny bit about this to my blog article: mainly, a link to a paper by Koide where he discusses some theories in which symmetries would prevent the lepton masses from depending on the energy scale. So he recognizes that this issue is important.
Peter Haggstrom says:
The inequality is a straight forward application of the Cauchy-Schwarz inequality:
With we get:
Squaring we get the LHS of the inequality:
The RHS is obtained by noting that:
Nice! Without loss of generality we can normalize the masses so their sum is one; by symmetry if the function assumes a minimum at a unique point on this triangle it must be the center, where the masses are equal, and there the function is 1/3. However, the trouble (as usual) with this argument is showing that there's a unique minimum; it seems just as easy to use Lagrange multiplier to find all the critical points, discover there's just one, and then investigate the function on the boundary of the triangle, where one or more of the masses is zero.
Yep. There are species of Cauchy-Schwarz and Arithmetic-Geometric mean problems which can be proved more laboriously with Lagrange multipliers.
Hans de Vries NL says:
Concerning your math puzzle:
The value 2/3 means that the vector h = {√me, √mμ, √mτ} has an angle of exactly 45° with the vector {1,1,1}. Any vector h on the 45° cone gives a value of 2/3.
For an arbitrary value of Q other than 2/3 the general formula for the this angle θ is given:
So for Q=2/3 this formula gives:
For Q=1/3 we get 0°, the minimum angle.
For Q=1 we get an angle of 54.73° which is the angle between {1,1,1} and any of {0,0,1} , {0,1,0} and {1,0,0}. If we go further then at least one of the three components becomes negative.
So the angle of θ=45° with respect to {1,1,1} is the geometric translation of Koïde's coincidence.
(and yes, we all do know how mass renormalization and all that is done in the textbooks I may suppose)
A Rivero says:
Robert Foot arXiv:hep-ph/9402242 A note on Koide's lepton mass relation
Neglect this post, it messes up the values 1/3 and 1. The other post corrects this.
Η σχέση Koide: μια μυστηριώδης εμπειρική εξίσωση – physicsgg says:
[…] Μια σχετική συζήτηση (που μας θύμισε την εξίσωση του Koide) γίνεται στην τελευταία ανάρτηση του John Carlos Baez ΕΔΩ. […]
westy31 says:
11 April, 2021 at 8:50 pm
The Koide formula reminds me of "The kiss precise".
The Koide formula (rewritten a bit):
(0 + m_e + m_mu + m_tau)^2 = 3/2 * (0 + m_e^2 + m_mu^2 + m_tau^2)
For 4 disks to exactly touch, the radii must satisfy:
(1/r0 + 1/r1 + 1/r3 + 1/r3)^2 = 2 * (1/r0^2 + 1/r1^2 + 1/r3^2 + 1/r3^2)
It turns out the factor 2 changes to a factor 3/2 if we demand the disks, instead of touching, intersect at an angle whose cosine is 2/3.
Also, we can set 1/r0 to zeo by making the circle a line (a circle of infinite radius)
So we get:
(0 + 1/r1 + 1/r3 + 1/r3)^2 = 3/2 * (0 + 1/r1^2 + 1/r3^2 + 1/r3^2)
The Koide formula can be visualised as a configuration of disks:
I made a little web sit one this:
https://westy31.home.xs4all.nl/KissPrecise/The%20Koide%20Formula%20and%20the%20Kiss%20Precise.html
I don't know if this brings us any closer to knowing if this formula is more than pure coincidence.
The value of 3/2 for the 1/cosine is special: 1/cos(alfa) is exactly equal to the factor that apears in the generalised Kiss precise formula.
Wolfgang says:
11 April, 2021 at 11:10 pm
When I once learned about the Koide formula it reminded me on this https://en.wikipedia.org/wiki/Descartes%27_theorem , but I was unable to formulate anything substantial about it. I liked the relation to geometric curvature though. Maybe this is related to your geometric explanation?
Well, I code-named Descartes' theorem "Kiss precise", so that at least is related.
To generalize Descartes' theorem to circles intersecting at an angle, I used a nice proof by Jerzy Kocik: https://arxiv.org/abs/1910.09174
He uses a map from disks with radius (r) and midpoint (x,y) to a (3+1)D Minkowski space. I vaguely see this as a clue. Also, I vaguely see lepton circles tiling event horizons in momentum space…
Robert A. Wilson says:
17 July, 2021 at 11:03 am
I first heard of the Koide formula from Marni Sheppeard, when I met her in Auckland in April 2015. I have always used it as a litmus test: if I can't explain the Koide formula, then I haven't found the right model yet. However, the CODATA 2014 value of the tau mass has reduced to , which makes the prediction less accurate than it was in 1992. At the same meeting in 2015, I told Marni that I had discovered that the sum of the three charged lepton masses plus three proton masses was equal to five neutron masses. Her response was "You don't actually believe that, do you?" In fact, I did believe it, and still do, because it predicts a tau mass of 1776.84. But now I have a dilemma: the Koide formula and my formula cannot both be correct, even if they do agree to 1 part in 10000.
17 July, 2021 at 6:28 pm
In fact, Marni came back to me at our next meeting a week or two later, and said that my formula wasn't quite correct. I didn't understand how she came to this conclusion, and I didn't pursue it at the time, but it seems likely that she was using the Koide value of the tau mass, rather than the experimental value, in which case her conclusion was indeed logically correct.
Ah yes we have here another peculiarity of Koide formula, that builds upon a peculiarity of electroweak theory: that the mass scale of electroweak particles happens to be in the same range that QCD mass scale. And then one half of the average of electron, tau and muon is about the same that one third of the average of neutron and proton. One could interpret this guessing that both sets of masses are generated from "current quark mass, 313 MeV", somehow. And one interpretation of your formula is that the "current mass" should be calculated considering the contribution of isospin breaking, this is, the mass difference between proton and neutron.
2 August, 2021 at 10:00 pm
Yes, that seems like a reasonable interpretation. My own interpretations are rather more radical, which I suppose is why few serious physicists pay any attention to them.
Well, if you are more radical that suggesting that QCD mass is related to yukawa-electroweak mass, then you have a really radical proposal :-D
Ha, ha! Try me! Have a look at my arXiv papers and see how radical you think I am.
A4 or S4 appear in Koide formula in a simple way. Consider the GUT limit where each family has a given mass, and it is composed of a tuple ([e,nu],[u-type,d-type]). We have three mass levels and any selection of three quarks choosing one of each family will meet Koide formula if electrón, muon and tau still meet it. So you have A4 lurking here. For instance put each generation quarks in opposite faces of a cube, and each vertex is a Koide formula for three quarks. Now, it happens that this symmetry is broken and some formulae remain more approximate than others: (tbc) (bcs) (csu) (sud), and perhaps (bcd).
For the argument to work, of course, you need the unbroken unified tuples to be not the expected ones, but [ub] [cd] [ts], This is not different to the argument used by Harari et al in the first paper having a Koide mass tuple.
The tell-tale phrase is "some are more approximate than others". As far as I am aware there are only two exact mass formulae: the Coleman-Glashow relation, and mine. All the rest are more or less approximate. And that includes the Koide formula.
A possible explanation for the discrepancy is that one of the two formulae is exact, for deep physical reasons, and the other is approximate, and depends on exactly how the underlying theory is gauged. My attempt to explain in detail how this might happen can be found in all the usual places.


text:
Home / Buhari / Coronavirus / national / COVID-19: Buhari orders prompt payment of salaries
COVID-19: Buhari orders prompt payment of salaries
Funso Adekitan April 02, 2020 Buhari, Coronavirus, national
President Muhammadu Buhari has charged the Ministry of Finance Budget and National Planning to ensure that Nigerian civil servants get their salaries paid promptly.
The President gave the directive on Thursday during a meeting with members of the Presidential Committee on the review of the Impact of the Novel Coronavirus (COVID-19) Pandemic on the Economy, held at the State House, Abuja.
Recapping details of the meeting to State House Correspondents after the meeting, Chairman of the Committee and Minister of Finance, Budget and National Planning, Mrs Zainab Ahmed, also said the President further directed that measures to protect the poor and the vulnerable are put in place.
She said the committee met with the President to update him on the developments instigated by the COVID-19 Pandemic globally and how much effect it has had on the nation's economy.
Speaking on the directives to issued at the meeting, she said besides ensuring prompt payment of civil servants' salaries, she said the President ordered the protection of critical national assets.
"Well, he has directed that we should make sure that salaries are paid, make critical infrastructures like roads, rails are protected, as much as possible use local inputs so that we retain value within our economy. And also make sure that we have measures that protect the poor and the vulnerable."
"This meeting was just to brief Mr. President as the situation we are in keeps evolving on a daily basis. As the health crisis gradually expands, affecting states and also the lockdown that has been ordered to help curtail the expansion of the health crisis.
"The consequences of the lockdown is the additional slowing down of the economy and the measures that we need to take to mitigate the negative consequences of the slow trade and businesses", she said.
Another member of the committee, Minister of State for Petroleum Resources, Chief Timipre Sylva, said the Committee had cause to meet with the President to keep him abreast of developments around the economy and the worsening fortunes at the international oil market.
Also speaking, another member of the committee, the Governor of the Central Bank of Nigeria (CBN), Mr Godwin Emefiele, said the committee had met with the President to suggest ways to redirect the economy so as to get it insulated against approaching global economic recession.
"The global economy naturally like we all know at this time will naturally suffer growth problems and may even lead to recession globally. So we are trying to see what we can do as a country to rescue our own situation so we don't go the direction many will go.
"It is not going to be easy but we can only assure our people that we are on top of it and that we will resolve it and Nigerians will still be better for it", he said.
COVID-19: Buhari orders prompt payment of salaries Reviewed by Funso Adekitan on April 02, 2020 Rating: 5
Tags: Buhari | Coronavirus | national


There are 695 posts in this topic. You are on page 1 of 14.
I know it's a bit early, but I thought I would start this topic. I enjoyed the MMR unboxings. I own a MMR LE and have ordered a AFM LE.
Exciting times. Open the box. The smell of new wood and fresh paint.
Anxiously awaiting AFMr LE #669 in Martian Green! CANT WAIT!!!!!
Nice LE number. I'm waiting for AFMr LE #851 to match my MMR.
Hope we see some starting to ship in a few weeks. Can't wait.
Something's bound to land any day now!
pin_guy mentioned his should arrive Monday or Tuesday... lucky bugger..!
Shipping was to supposedly start in May...We shall see. Hopefully in another year or so ill be able to grab one of these after seeing how they hold up. There weren't many (if any) real issues with MMR, were there?
A few. Labnip did a good job documenting all the issues that came up.
Can't wait for that NIB smell. I hope I'm in the first LE run.
I am hoping to receive an email soon about shipment, excited for my special edition!
The AFMrLE at pinagogo seemed to be rock solid the whole weekend. It was played non stop the entire time, and I never saw it go down at all. I saw other new games go down a few times. I have read that it was solid at TPF as well.
It seems like the manufacturers may be getting these things way more reliable.
I don't know if MMr was able to do that at shows leading up to launch or not. I remember WOZ constantly needing work at shows when it was launching, but it looks like they have solidified their games too. I only saw dialed in go down once during the show, and that was only due to a spectacular beheading of one of the playfield toys. I was impressed with how stable the game was.
I'm not advocating being irresponsible with your cash, but that's part of what savings are for. Saving up for things. Now as long as you don't drop it below your emergency funds level of 3-6 months living expenses plus funds for the unexpected, why not?
Just lining up in this thread. Paid the deposit last week and got notification of shipping yesterday (SE version). I was not expecting anything to drop before Christmas.
I purchased through PPS. Final payment was sent and received. Im told there will be a tracking number shortly for my SE. Ill post updates and pictures as I can.
I was at TPF all weekend this year and can confirm that all 3 models of AFMr were rock solid the entire time.
I thought LEs where shipping first after a batch of SEs where being shipped to vendors for display games? Pretty cool that you put a deposit down last week and are getting your SE so quickly. Congrats!
I think it was 100 SEs first.
We have different levels of savings. If I had more than a safety net right now, this would have been ordered the day I played it at PAGG.
No love for the "Classic" wtf?
The first 2 Special Editions off the line at the Nitro booth / NW Pinball Show!
Now as long as you don't drop it below your emergency funds level of 3-6 months living expenses plus funds for the unexpected, why not?
I had this all wrong, I thought 3-6 pins over 3-6 months.
LOL well clearly you're wealthy, most of us are not.
If I had 5 years in savings, I have a pretty good idea when the job would go away for a little while.
And that would be after I paid off the house.
We have different levels of savings.
Check out the digit app. It's a passive way to save that debits small amounts from your checking account depending on your spending habits and account balance. You don't even notice the withdrawals.
Please post pics when you get it. Very cool I can't wait. I hope I get the 30 days out call soon.
Put my deposit down for the LE last week, AFM was always one of my top tier machines to own someday. My vendor was nice enough to ward me off of a nice used one he got in a while back by letting me know the remakes were coming. Opinion time from you guys though, I'm trying to decide between the martian green trim and the following custom blends, what do you think?
I like the red and black, but CGC is not offering this as an option right? If you were going to go with your own powder coating, then I would just skip getting the LE, since that is already included, and just get the SE instead and then do custom powder coating.
I am getting my LE in all black.
Green is the only way go! (Unless of course you like black or stainless).
Apologies I should've clarified, the blends are just custom options I was discussing with my vendor on the LE. I wanted the bigger color DMD with the SE and when I saw that I could get the LE for another $500 and get all the extra goodies(tri color mini saucers/that epic topper/mirror blades etc) I figured why not. I'm pretty sure I'm sticking with the green, it's garish and corny looking which I think is perfect for the theme of the machine.
My shipment was delayed a week due to "lack of manuals" but I was contacted by the shipping company today so I know its coming for sure now! My SE was just picked up from CGC and is being drop shipped with a delivery scheduled for tomorrow. I'll post pics of the unboxing....better charge my camera battery.
I just got the balance invoice for my AFM LE 851. BTW big smile on my face . Countdown to big fun and bigger smile.
SN 1034 delivered, will post more pics when I actually take it out of the box.
I just wired the money for mine, decided to go for the SE as well. Ships this week, I can't wait. Would be so killer if you could post a quick video of yours all lit up, congrats and enjoy!
I can hear my original plummeting in value, and I couldn't care less. So great to see this pin getting a mass release FINALLY, and I am so happy to see this community get a real shot at owning this game.
Now...here's your goal. Took me right at one year to do!
AFMSE has landed at Tilt Pinball Bar in Minneapolis. Dialed-In showed up a couple of days later too. Both are only $.25 to play too.
Lol still plenty of people who like a nice original ..trust me. I cld still sell mine for a fair amount more than i have in it but its a amazing game and it wld be last to go. Still im glad all these great classics are being done so more can enjoy them . They are still very expensive imo but they are selling ..so thats what matters. I really hope cc , bbb or kp is next bc they are very rare and way to expensive.
I hope those are next as well. I don't want any of them, and the last thing I need at the moment is another expensive pin that I want. lol That could give me time to save up for an MMr after AFMr before (hopefully) MB is out.
Those would be good to get out for the people who want them though, and would probably sell really well. I am interested to see if those games are as popular after the rarity is taken out of the equation. They are at #29, #44, and #79 on the top 100 right now.
Got home from work and went right to setting it up, I was glad to see that CGC put the leg bolts in the mounting holes, this made it so much easier to setup vs having the bolts in the cash box like my MMr was.
Stood it on its back and put on the front legs, set it on its front legs and lifted this bad boy up, wife was nice enough to slide my saw horse under it so I can set it down to put on the back legs.
Opened the coin door to get the head bolts from the coin box and ... holy cow I see coin mechs!
Inspected everything ... First thing I noticed that I didn't care for is there is essentially 0 clearance between the bottom of the back glass and top of the speaker panel, I just had to pry it out. Once out I tried to press the back glass edge molding on tighter, it didn't seem to move, but the backglass did go in easier than it came out.
The video looks like crap unless you download it to play it ... this could have been my browser settings, it looked fine once I set it to 1080p.
Overall I have the say the game is beautiful! The LED are very bright and clear which is typical of LEDs of course, CGC included multiple fade options to customize to your liking, I left mine on the default slow fade to simulate the effects of incandescent lamps, you can see these effects in the video. The thing that really got my attention was the sound, simply outstanding! You have to hear it in person to really appreciate it.
Overall I have the say the game is beautiful! The LED are very bright and clear which is typical of LEDs of course, CGC included multiple fade options to customize to your liking, you can see these effects in the video, I left mine on the default slow fade to simulate the effects of incandescent lamps. The thing that really got my attention was the sound, simply outstanding, you have to hear it to really appreciate it.
Did they change the gi sockets? I thought these were the same as mmr and original? It looks like a plug?
What did CGC end up putting in for 'cliffy' protectors in AMFr LE?


text:
Home > News > International
Time to expose the Pak's corrupt dictatorship: US Congressman
null | 14 July 2018 12:39 PM GMT
United States US Congressman Dana Rohrabacher on Friday expressed his ire over the InterServices Intelligences ISI blatant atrocities against its own...
Washington D. C. [USA]: United States (US) Congressman Dana Rohrabacher on Friday expressed his ire over the Inter-Services Intelligence's (ISI) blatant atrocities against its own people, the crimes that Pakistan is committing and the corruption that feeds the system.
While stating his solidarity with members of the Muttahida Qaumi Movement (MQM) who gathered at the Capitol Hill in Washington DC today, Rohrabacher articulated that the people of United States must be told that the Government in Islamabad and the ISI, in particular, are not the allies of a free world.
"The United States opposes the corrupt oppressors in Islamabad", the congressman said.
Speaking at the Mohajir Day at the Capitol Hill - The Future of Mohajir Nation, Rohrabacher said that it was time for the international community to step in against Pakistan.
"First thing we can do is to make sure that we (US) will never send Pakistan another weapon that they can use against their own people, that's the first start," Rohrabacher said.
While expressing his disgust over the wrongdoings of the ISI in Pakistan, Rohrabacher assured the members of the MQM of his full support and pledged to raise these issues in the US Congress and other forums.
He also suggested that the city of Karachi should become independent and a city-state should be recognized and dealt with on the international stage.
It should be noted that Rohrabacher is known for his anti-Pakistan stance in the US Congress.
In 2012, he had said the government of Pakistan was radical and supported the Taliban, thereby was an enemy of US and freedom. Rohrabacher was also one of the two congressmen who moved a bill in 2016 for the US to declare Pakistan 'a terrorist state'.
Dana Rohrabacher
InterServices Intelligence
Muttahida Qaumi Movement