A Chernoff Bound for Random Walks on Expander Graphs
DOI10.1137/S0097539794268765zbMATH Open0911.60016OpenAlexW2139964991WikidataQ29300692 ScholiaQ29300692MaRDI QIDQ4210091FDOQ4210091
Authors: David Gillman 
Publication date: 20 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539794268765
Recommendations
graphentropyrandom walkmatchinglarge deviationseigenvaluepartition functionapproximate countingIsing systemexpanderMarkov source
Markov processes: estimation; hidden Markov models (62M05) Large deviations (60F10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Analysis of algorithms and problem complexity (68Q25) Source coding (94A29)
Cited In (42)
- Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications
- Imperfect gaps in Gap-ETH and PCPs
- The Swendsen–Wang dynamics on trees
- A matrix expander Chernoff bound
- Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
- Title not available (Why is that?)
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Testing the \((s,t)\) connectivity of graphs and digraphs
- Occupation measure for random walk on the circle
- DEX: self-healing expanders
- Fixed Precision MCMC Estimation by Median of Products of Averages
- A local central limit theorem for random walks on expander graphs
- Tail Estimates for Sums of Variables Sampled by a Random Walk
- Estimating graph parameters with random walks
- Approximate and dynamic rank aggregation
- Cutoff for random walk on dynamical Erdős-Rényi graph
- Local correctability of expander codes
- Function-specific mixing times and concentration away from equilibrium
- An introduction to randomness extractors
- Uniform Chernoff and Dvoretzky-Kiefer-Wolfowitz-type inequalities for Markov chains and related processes
- Random walks on rotating expanders
- Expander graphs and their applications
- Approach to equilibrium for random walks on graphs and for stochastic infinite particle processes
- Finding large expanders in graphs: from topological minors to induced subgraphs
- The Littlewood-Offord problem for Markov chains
- The worm process for the Ising model is rapidly mixing
- Mixing time estimation in reversible Markov chains from a single sample path
- A Hoeffding inequality for Markov chains
- Mixing of the upper triangular matrix walk
- Nonasymptotic bounds on the estimation error of MCMC algorithms
- Title not available (Why is that?)
- On sufficient conditions for spanning structures in dense graphs
- Typically-correct derandomization for small time and space
- Random walks on hyperbolic spaces: concentration inequalities and probabilistic Tits alternative
- Cover time of a random graph with a degree sequence. II: Allowing vertices of degree two.
- Distributed protocols against mobile eavesdroppers
- Efficient Simulation of High Dimensional Gaussian Vectors
- Rigorous confidence bounds for MCMC under a geometric drift condition
- Logarithmic reduction of the level of randomness in some probabilistic geometric constructions
- Linear cover time is exponentially unlikely
- Optimal Hoeffding bounds for discrete reversible Markov chains.
- Concentration of Markov chains with bounded moments
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)
