Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BERNSTEIN:
Reports tagged with Bernstein:
TR26-216 | 26th September 2026
Zhao Song

Matrix Hoeffding and Bernstein Bounds with Sharp Constants for Markov Chains

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 ... more >>>




ISSN 1433-8092 | Imprint