Compression algorithms for low-complexity strings?
No, at least not in the TM model, i.e., for Kolmogorov complexity. Given $g(x) \leq f(x) \leq |x|$ for all $x$ where $g$ is monotonic and unbounded and $f$ is recursive, it is not possible to enumerate an infinite subset of $\{ x : K(x) &gt; f(x)\}$. 

Suppose for the sake of contradiction there exists a recursive function $h$, the low-complexity compression algorithm, which on input $x$ outputs a TM that reproduces $x$ and has the following additional property: Let $A:\mathbb{N} \rightarrow \mathbb{N}$ and $B:\mathbb{N} \rightarrow \mathbb{N}$ be given such that both are recursive, $A(|x|) \leq B(|x|) \leq |x|$ for all $x$, and $A$ is unbounded. Then $\forall x, K(x) \leq A(|x|) \implies |h(x)| \leq B(|x|)$.

Now choose $f(x) = A(|x|)$. We wish to enumerate an infinite subset of $\{x: K(x) &gt; A(|x|)\}$. Note that there are infinite $x$ such that $K(x) &gt; B(|x|)$ because $B(|x|) \leq |x|$. For any such $x$, $|h(x)| \geq K(x)$ by the definition of $K$ so $|h(x)| &gt; B(|x|)$. Then for a generic string $x$, $|h(x)| &gt; B(|x|) \implies K(x) &gt; A(|x|)$ and we can enumerate an infinite subset of $\{x: K(x) &gt; A(|x|)\}$, a contradiction.