20 problems

Asymptotic normalized-information conjecture. As $n\to+\infty$, the function $S_\infty(n)$ converges to a constant $S_\infty$ whose value is approximately $3.5$.

Unbiased and uncorrelated components conjecture. The components of $\vec{s}$ should preferably be unbiased and uncorrelated in order to minimise loss of information in the original…

Let $t_i$ be the token at position $i$, let $H_i=H(t_i\mid t_{<i})$ be its conditional entropy, and let $\mathcal{T}$ be the LAWS trie with description length $L(\mathcal{T})$. Opt…

The paper considers integers and encoded values represented through wavelet trees, with reversed indexes used to recover or approximate the corresponding values. Reversed Indexes a…

Let an entropy encoder receive a sequence of $n$ numbers from the alphabet $\{0,1,\ldots,\sigma-1\}$. The redundancy is the difference between the number of bits produced by the en…

The lower-bound conjecture. Even without assumption (A3), every such adaptive scheme satisfies

The variables $X$, $Y$, and $Z$ describe, respectively, input data, a binary classification target, and a finite-valued compressed representation of $X$. Shannon's entropy of the r…

Exponent-improvement conjecture. The achievability bound can be further improved to $E_\mathrm{r}$.

Conditional binary AIFV-$m$ redundancy conjecture. Under certain conditions on the size of the source alphabet, the worst-case redundancy of optimal binary AIFV-$m$ codes is

Binary AIFV-$m$ upper-bound conjecture. For every source, the redundancy of an optimal binary AIFV-$m$ code is at most

Binary AIFV-$m$ redundancy conjecture. For every natural number $m$, the worst-case redundancy of optimal binary AIFV-$m$ codes is

Extended AIFV redundancy conjecture. When the alphabet is sufficiently large relative to $m$, the worst-case redundancy of optimal extended binary AIFV codes is

Yamamoto's conjecture. Binary AIFV codes might attain better compression performance when more code trees are allowed to be used.

Let $J_n(X)$ be the proposed estimator of the entropy rate of a stationary and ergodic process $X$, and let $I(\epsilon)$ be the rate function appearing in the established converge…

RSSS zero-size subset overhead conjecture. The overhead of textsc{rsss} relative to the range-narrowing codes is at least partly due to its often needing to explicitly encode zero-…

Square-root redundancy conjecture. This scheme has $O(\sqrt n)$ rescales, and its redundancy with respect to a piecewise stationary model with partition ${\mathcal S}$ is

Entropy–tablebase bound. The relation

Let $\mathcal{X}$ be a data alphabet, let $f(n)$ be a function, and let $C$ be an $(\mathcal{X},f(n))$-super-universal computable code. For an infinite data sequence $\bm{x}$, defi…

Common-phenomenon conjecture. The observation that rare events can be discarded without harming the utilities under consideration should be a common phenomenon rather than being sp…

Conjecture on real-life data compressors. The same results can be proven for some particular real-life data compressors, for example those based on the measure $R$ or on the LZ alg…