R\'enyi divergence guarantees for hashing with linear codes
<|reference_start|>R\'enyi divergence guarantees for hashing with linear codes: We consider the problem of distilling uniform random bits from an unknown source with a given $p$-entropy using linear hashing. As our main result, we estimate the expected $p$-divergence from the uniform distribution over the ensemble of random linear codes for all integer $p\ge 2$. The proof relies on analyzing how additive noise, determined by a random element of the code from the ensemble, acts on the source distribution. This action leads to the transformation of the source distribution into an approximately uniform one, a process commonly referred to as distribution smoothing. We also show that hashing with Reed-Muller matrices reaches intrinsic randomness of memoryless Bernoulli sources in the $l_p$ sense for all integer $p\ge 2$.<|reference_end|>
@article{pathegama2024r\'enyi,
    title={R\'enyi divergence guarantees for hashing with linear codes},
    author={Madhura Pathegama and Alexander Barg},
    journal={arXiv preprint arXiv:2405.04406},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.04406},
    primaryClass={cs.IT math.IT}
}