Hardness of comparing two run-length encoded strings

In this paper, we consider a commonly used compression scheme called run-length encoding. We provide both lower and upper bounds for the problems of comparing two run-length encoded strings. Specifically, we prove the 3sum-hardness for both the wildcard matching problem and the k$k$-mismatch problem with run-length compressed inputs. Given two run-length encoded strings of m$m$ and n$n$ runs, such a result implies that it is very unlikely to devise an o(mn)$o\left(mn\right)$-time algorithm for either of them. We then present an inplace algorithm running in O(mnlogm)$O(mnlogm)$ time for their combined problem, i.e. k$k$-mismatch with wildcards. We further demonstrate that if the aim is to report the positions of all the occurrences, there exists a stronger barrier of Ω(mnlogm)$\Omega (mnlogm)$-time, matching the running time of our algorithm. Moreover, our algorithm can be easily generalized to a two-dimensional setting without impairing the time and space complexity.     

Stable extendibility of vector bundles over real projective spaces

Let F$\mathbb{F}$ be either the real number field R$\mathbb{R}$ or the complex number field C$\mathbb{C}$ and RPⁿ${\mathbb{RP}}^n$ the real projective space of dimension n. Theorems A and C in Hemmi and Kobayashi (2008) [2] give necessary and sufficient conditions for a given F$\mathbb{F}$-vector bundle over RPⁿ${\mathbb{RP}}^n$ to be stably extendible to RP^m${\mathbb{RP}}^m$ for every m?n$m?n$. In this paper, we simplify the theorems and apply them to the tangent bundle of RPⁿ${\mathbb{RP}}^n$, its complexification, the normal bundle associated to an immersion of RPⁿ${\mathbb{RP}}^n$ in R^n+r${\mathbb{R}}^{n+r}$(r>0)$(r>0)$, and its complexification. Our result for the normal bundle is a generalization of Theorem A in Kobayashi et al. (2000) [8] and that for its complexification is a generalization of Theorem 1 in Kobayashi and Yoshida (2003) [5].