Paper 2026/1719
Matrix Hoeffding and Bernstein Bounds with Sharp Constants for Markov Chains
Abstract
Matrix concentration for Markov chains was initiated in the expander-walk setting by Garg, Lee, Song, and Srivastava'18 [GLSS18]. However, the constant obtained in [GLSS18] is quite loose, and it is natural to ask whether a tighter proof can yield the same constant as in the independent matrix concentration setting. In this paper, we provide a positive answer to this question. Our Hoeffding exponent is sharp, as shown by a scalar obstruction. Our Chernoff and Bernstein constants improve upon those in [GLSS18] and Neeman, Shi, and Ward'24 [NSW24], respectively.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- de-randomizationmatrix chernoffmatrix hoeffdingmatrix bernstein
- Contact author(s)
- magic linuxkde @ gmail com
- History
- 2026-08-20: approved
- 2026-08-18: received
- See all versions
- Short URL
- https://ia.cr/2026/1719
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2026/1719,
author = {Zhao Song},
title = {Matrix Hoeffding and Bernstein Bounds with Sharp Constants for Markov Chains},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1719},
year = {2026},
url = {https://eprint.iacr.org/2026/1719}
}
