Fetching the paper…
Reading the bibliography…
We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander, confirming a conjecture due to Wigderson and Xiao.
A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations
Herman Chernoff · 1952
Earlier work this paper cites.
Lower bounds for the Helmholtz function
Sidney Golden · 1965
Earlier work this paper cites.
Inequality with applications in statistical mechanics
Colin J Thompson · 1965
Earlier work this paper cites.
Functions of one Complex Variable
John B. Conway · 1978
Earlier work this paper cites.
Ramanujan graphs
Alexander Lubotzky, Ralph Phillips, and Peter Sarnak · 1988
Earlier work this paper cites.
Matrix analysis
Rajendra Bhatia · 1997
Earlier work this paper cites.
Large deviation bounds for Markov chains
Nabil Kahale · 1997
Earlier work this paper cites.
A chernoff bound for random walks on expander graphs
David Gillman · 1998
Earlier work this paper cites.
Chernoff-type bound for finite Markov chains
Pascal Lezaud · 1998
Earlier work this paper cites.
Random vectors in the isotropic position
Mark Rudelson · 1999
Cited alongside, same era.
Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors
Omer Reingold, Salil Vadhan, and Avi Wigderson · 2000
Cited alongside, same era.
Strong converse for identification via quantum channels
Rudolf Ahlswede and Andreas Winter · 2002
Cited alongside, same era.
Optimal Hoeffding bounds for discrete reversible Markov chains
C. A. Leon and F. Perron · 2004
Cited alongside, same era.
A randomness-efficient sampler for matrix-valued functions and applications
Avi Wigderson and David Xiao · 2005
Cited alongside, same era.
Concentration inequalities and martingale inequalities: a survey
Fan Chung and Linyuan Lu · 2006
Cited alongside, same era.
Tail estimates for sums of variables sampled by a random walk
R. Wagner · 2008
Later among the works it cites.
Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications
Avi Wigderson and David Xiao · 2008
Later among the works it cites.
Chernoff-Hoeffding bounds for Markov chains: Generalized and simplified
Kai-min Chung, Henry Lam, Zhenming Liu, and Michael Mitzenmacher · 2012
Later among the works it cites.
User-friendly tail bounds for sums of random matrices
Joel A Tropp · 2012
Later among the works it cites.
Probability in Banach Spaces: isoperimetry and processes
Michel Ledoux and Michel Talagrand · 2013
Later among the works it cites.
An introduction to matrix concentration inequalities
Joel A. Tropp · 2015
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Retraction of Wigderson-Xiao: A randomness-efficient sampler for matrix valued functions, eccc tr05-107. 2006
Avi Wigderson and David Xiao · 2006
Cited alongside, same era.
Classical Fourier Analysis
Loukas Grafakos · 2008
Cited alongside, same era.
Randomness-efficient sampling within NC1
Alexander D Healy · 2008
Cited alongside, same era.
Later among the works it cites.
Generalized log-majorization and multivariate trace inequalities
Fumio Hiai, Robert Koenig, and Marco Tomamichel · 2016
Later among the works it cites.
A sharp tail bound for the expander random sampler
Shravas Rao and Oded Regev · 2017
Closest in time.
Multivariate trace inequalities
David Sutter, Mario Berta, and Marco Tomamichel · 2017
Closest in time.