A matrix expander Chernoff bound

DOI10.1145/3188745.3188890zbMath1442.60007arXiv1704.03864OpenAlexW2797316125MaRDI QIDQ5230365

Zhao Song, Nikhil Srivastava, Ankit Garg, Yin Tat Lee

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

random walksderandomizationGolden-Thompson inequalityexpander graphChernoff boundmatrix concentration

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Sums of independent random variables; random walks (60G50)

Related Items (4)

A Hoeffding inequality for Markov chains ⋮ Unnamed Item ⋮ Concentration of Markov chains with bounded moments ⋮ From Poincaré inequalities to nonlinear matrix concentration

This page was built for publication: A matrix expander Chernoff bound