{"id":"arxiv/2601.06688","url":"https://arxiv.org/abs/2601.06688","tags":["cs.IT","math.ST"],"score":0,"title":"The Sample Complexity of Lossless Data Compression","domain":"cs.IT","source":"arxiv","authors":["Terence Viaud","Ioannis Kontoyiannis"],"reviews":0,"subject":"cs.IT","summary":"A new framework is introduced for examining and evaluating the fundamental limits of lossless data compression, that emphasizes genuinely non-asymptotic results. The {\\em sample complexity} of compressing a given source is defined as the smallest blocklength at which it is possible to compress that source at a specifically constrained rate and to within a specified excess-rate probability. This formulation parallels corresponding developments in statistics and computer science, and it facilitates the use of existing results on the sample complexity of various hypothesis testing problems. For…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-10","reactions":{}}