Bounds from a card trick

DOI10.1016/j.jda.2011.08.001zbMath1267.68111arXiv1011.4609OpenAlexW1988637266MaRDI QIDQ414410

Travis Gagie

Publication date: 11 May 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.4609

zbMATH Keywords

empirical entropyestimating entropyMarkov sources

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Measures of information, entropy (94A17)

Cites Work

• Unnamed Item
• Unnamed Item
• Large alphabets and incompressibility
• Compressed representations of sequences and full-text indexes
• On the Complexity of Computational Problems Regarding Distributions
• An analysis of the Burrows—Wheeler transform
• Space-Conscious Compression
• Universal Entropy Estimation Via Block Sorting
• Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
• On the Value of Multiple Read/Write Streams for Data Compression
• Estimating the unseen
• Elements of Information Theory
• The Complexity of Approximating the Entropy