Wee, Hoeteck

A source is compressible if we can efficiently compute short

descriptions of strings in the support and efficiently

recover the strings from the descriptions. In this paper, we

present a technique for proving lower bounds on

compressibility in an oracle setting, which yields the

following results:

- We ...
more >>>

Shuichi Hirahara, Rahul Ilango, Ryan Williams

A compression problem is defined with respect to an efficient encoding function $f$; given a string $x$, our task is to find the shortest $y$ such that $f(y) = x$. The obvious brute-force algorithm for solving this compression task on $n$-bit strings runs in time $O(2^{\ell} \cdot t(n))$, where $\ell$ ... more >>>