It depends on the precise definition of RAM being used, but (for most reasonable definitions of RAMs) this would also imply that SAT is not solvable in $O(n^{2-e})$ time by multitape TMs, a longstanding open problem.
The reason is that there is a very efficient reduction from linear time on RAMs to SAT (in general, nondeterministic quasi linear time on RAMs is the same as nondeterministic quasi linear time on multitape TMs.)
I have never seen the above reference before, and I would be skeptical if it never appeared in a journal or conference, but it could be worth checking to see if it implies a SAT lower bound as well. Interesting find!
UPDATE: I looked at the paper at your link above briefly this morning. The claimed hard function is a complicated partial match query problem. Essentially there is a notion of a "string pattern" and one is given a bunch of binary strings and asked to determine which strings fit the pattern (and which don't). Let me write out the definition of the function, as I understand it. I will use different symbols and terminology to try to make the definition easier to understand.
The set of "string templates" (the author's $U$, Definition 5.1) is a set of strings over $\{0,1,end,branch\}$, defined recursively:
- $end \in U$
- $\alpha \in U$ implies $0\alpha, 1\alpha \in U$
- $\alpha, \beta \in U$ implies $branch~ \alpha \beta \in U$.
Note that every string ends in an $end$ symbol. The $branch$ is used to denote a possible choice in the match: either $\alpha$ can be matched as a partial string, or $\beta$, and $end$ is used at the end of $\alpha$ to signal where $\alpha$ ends and $\beta$ begins.
We say that a binary string $x$ "matches" a string template $\alpha \in U$ (the author's Definition 5.2) if $x$ is in the set $\phi(\alpha)$, recursively defined as:
- $\phi(end) = \epsilon$ ($end$ symbols are removed)
- $\phi(b\alpha) = b \phi(\alpha)$ for $b \in \{0,1\}$ (normal string matching)
- $\phi(branch~ \alpha \beta) = 0\phi(\alpha) \cup 1 \phi(\beta)$, for $\alpha,\beta \in U$.
The third condition is the main one here: the author intends for us to find the $end$ symbol that "matches up" with the first $branch$ symbol, and partition $\alpha$ and $\beta$ according to that. Then, depending on whether the next symbol of $x$ is $0$ or $1$, the next piece of $x$ should either partial-match to $\alpha$ or partial-match to $\beta$.
It should be analogous to think of an $\alpha$ as an encoding of a (rooted) binary tree (each node has at most two children), where we label each edge of the tree by $0$ or $1$, and we say that a string $x$ matches the tree if there's some root-to-leaf path whose concatenated symbols are exactly $x$.
Anyway, the final presumed hard function $g$ (Definition 5.2) is:
Given a string template $\alpha \in U$ and given binary strings $x_1,\ldots,x_k$ (where each string is separated by a new symbol) output $k$ bits indicating which $x_i$'s match the template $\alpha$.
If this was a "normal" partial match query problem (e.g. with strings over $\{0,1,\star\}$, then it would be easily computed in $O(n)$ time on a multitape Turing machine, even one that just reads its input in one direction. I don't see why computing multiple queries on a binary search tree should take super-linear time for a multitape Turing machine. (I don't see why following $K$ paths down a binary tree of description size $N$ should take more than $(N+K) \cdot poly(\log(KN))$ time.) And the fact that it didn't appear in a major conference or a major journal makes me very suspicious. (It does appear in a journal: https://www.ems-ph.org/journals/show_pdf.php?issn=0034-5318&vol=13&iss=2&rank=5) But I didn't spend more than an hour looking at this!
FINAL UPDATE: Brynmor Chapman looked at this paper more closely, and observed the proof only gives a lower bound for the "on line" version of the function, where the query for each binary string $x_i$ (as described above) must be answered (the TM must output a bit) before the TM is allowed to read the next binary string $x_{i+1}$. This a data structure lower bound for TMs, which is much easier to prove given the 1-dimensional nature of TM tapes. That is, the lower bound proved is much weaker than what is claimed: that there is a function $g$ computable in linear time on RAMs which requires nearly quadratic time on a multi-tape Turing machine. As far as I know, that claim remains open.
