MathDB6 problems
- 0 votes0 replies0 views
Tightness conjecture for the LMI rate and entropy-coded index entropy
LMI-rate tightness conjecture. The asymptotic conditional entropy of the entropy-coded matching-codeword index equals the LMI rate:
- 0 votes0 replies0 views
Optimality conjecture for finite-state lossy encoders with exponentially many states
Optimality conjecture. The performance achieved by this construction is the best performance achievable for sufficiently large .
- 0 votes0 replies0 views
Conjecture on sub-dominant algorithmically relevant clusters in lossy compression
In the zero-temperature landscape for lossy compression, consider the clusters of solutions arising in the regime where the clusters are point-like and difficult for algorithms to…
- 0 votes0 replies0 views
Approximate matching conjecture for near-linear Lempel–Ziv lossy compression
Approximate matching conjecture. The approximate matching procedure could reduce the algorithm's complexity from quadratic time to linear time, up to logarithmic factors, without s…
- 0 votes0 replies0 views
The SPARC rate-distortion conjecture under minimum-distance encoding
SPARC rate-distortion conjecture. SPARCs achieve the optimal rate-distortion trade-off for all rates with minimum-distance encoding.
- 0 votes0 replies0 views
Uncorrelated codewords as a necessary condition for achieving the Shannon limit
For a lossy compression scheme, let denote the Edwards–Anderson order parameter measuring correlations among codewords in codeword space. Uncorrelated-codeword conjecture. The…