A Chernoff Bound for Random Walks on Expander Graphs
From MaRDI portal
(Redirected from Publication:4210091)
Recommendations
Cited in
(53)- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Optimal Hoeffding bounds for discrete reversible Markov chains.
- Approximate and dynamic rank aggregation
- Occupation measure for random walk on the circle
- Cutoff for random walk on dynamical Erdős-Rényi graph
- The Littlewood-Offord problem for Markov chains
- Random walks on hyperbolic spaces: concentration inequalities and probabilistic Tits alternative
- Function-specific mixing times and concentration away from equilibrium
- Concentration of Markov chains with bounded moments
- Estimating graph parameters with random walks
- Mixing time estimation in reversible Markov chains from a single sample path
- Local correctability of expander codes
- Nonasymptotic bounds on the estimation error of MCMC algorithms
- Logarithmic reduction of the level of randomness in some probabilistic geometric constructions
- DEX: self-healing expanders
- A Hoeffding inequality for Markov chains
- Finding large expanders in graphs: from topological minors to induced subgraphs
- Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications
- An introduction to randomness extractors
- Tail Estimates for Sums of Variables Sampled by a Random Walk
- Expander graphs and their applications
- Mixing of the upper triangular matrix walk
- Approach to equilibrium for random walks on graphs and for stochastic infinite particle processes
- Testing the \((s,t)\) connectivity of graphs and digraphs
- Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
- The worm process for the Ising model is rapidly mixing
- Typically-correct derandomization for small time and space
- Imperfect gaps in Gap-ETH and PCPs
- Deterministic approximation of random walks in small space
- Uniform Chernoff and Dvoretzky-Kiefer-Wolfowitz-type inequalities for Markov chains and related processes
- Efficient Simulation of High Dimensional Gaussian Vectors
- A matrix expander Chernoff bound
- Cover time of a random graph with a degree sequence. II: Allowing vertices of degree two.
- Fixed Precision MCMC Estimation by Median of Products of Averages
- scientific article; zbMATH DE number 7650126 (Why is no real title available?)
- scientific article; zbMATH DE number 7758327 (Why is no real title available?)
- On sufficient conditions for spanning structures in dense graphs
- The Swendsen–Wang dynamics on trees
- Distributed protocols against mobile eavesdroppers
- Rigorous confidence bounds for MCMC under a geometric drift condition
- Random walks on rotating expanders
- A local central limit theorem for random walks on expander graphs
- Linear cover time is exponentially unlikely
- Quantum expanders and property (T) discrete quantum groups
- Parameterized inapproximability for Steiner orientation by gap amplification
- Derandomization with pseudorandomness
- Modularity and graph expansion
- Almost-Ramanujan expanders from arbitrary expanders via operator amplification
- The expander hitting property when the sets are arbitrarily unbalanced
- Spectral gap of nonreversible Markov chains
- Pseudobinomiality of the sticky random walk
- An efficient coding theorem via probabilistic representations and its applications
- Towards a Banach space Chernoff bound for Markov chains via chaining arguments
This page was built for publication: A Chernoff Bound for Random Walks on Expander Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210091)
