A Chernoff bound for random walks on expander graphs

No abstract is available for this paper.

• Publication year

  1993

• Venue

  Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science

• Publication date

  1993-11-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/SFCS.1993.366819
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Probability Inequality for the Occupation Measure of a Reversible Markov Chain

  1995influential reference
• Random Walks in a Convex Body and an Improved Volume Algorithm

  1993influential reference
• Hidden Markov chains: convergence rates and the complexity of inference

  1993cited by this paper
• Matchings in lattice graphs

  1993cited by this paper
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow

  1992cited by this paper
• Eigenvalue bounds on convergence to stationarity for nonreversible markov chains

  1991cited by this paper
• Computing the volume of convex bodies : a case where randomness provably helps

  1991cited by this paper
• Matrix Perturbation Theory

  1990cited by this paper
• A large deviations approach to error exponents in source coding and hypothesis testing

  1990cited by this paper
• Polynomial-Time Approximation Algorithms for the Ising Model

  1990cited by this paper
• Security preserving amplification of hardness

  1990cited by this paper
• Large Deviation Lower Bounds for Additive Functionals of Markov Processes

  1990cited by this paper
• How to recycle random bits

  1989cited by this paper
• Dispersers, deterministic amplification, and weak random sources

  1989cited by this paper
• Approximating the Permanent

  1989cited by this paper
• A random polynomial time algorithm for approximating the volume of convex bodies

  1989cited by this paper
• Finite-time implications of relaxation times for stochastically monotone processes

  1988cited by this paper
• Deterministic simulation in LOGSPACE

  1987cited by this paper
• Limit Theorems for Harris Markov Chains, I

  1987cited by this paper
• On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing

  1987influential reference
• Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains

  1987influential reference
• Random Generation of Combinatorial Structures from a Uniform Distribution

  1986cited by this paper
• How hard is it to marry at random? (On the approximation of the permanent)

  1986cited by this paper
• Eigenvalues and expanders

  1986influential reference
• Large deviations, hypotheses testing, and source coding for finite Markov chains

  1985cited by this paper
• lambda1, Isoperimetric inequalities for graphs, and superconcentrators

  1985cited by this paper
• Explicit Concentrators from Generalized N-Gons

  1984cited by this paper
• Monte-Carlo algorithms for enumeration and reliability problems

  1983cited by this paper
• A Short Introduction to Perturbation Theory for Linear Operators

  1982cited by this paper
• Complex Analysis

  1979cited by this paper
• Central limit theorems and statistical inference for finite Markov chains

  1974cited by this paper
• On the Computation of Multidimensional Integrals by the Monte-Carlo Method

  1971cited by this paper
• On nonnegative matrices

  1971cited by this paper
• The algebraic eigenvalue problem

  1966cited by this paper
• More Exact Statement of Limit Theorems for Homogeneous Markov Chains

  1961cited by this paper
• Asymptotic Rate of Discrimination for Markov Processes

  1960cited by this paper
• Stochastic processes

  1953cited by this paper
• On the Theory of the Ising Model of Ferromagnetism

  1953cited by this paper
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

  1952cited by this paper

• Matrix Chernoff concentration bounds for multipartite soft covering and expander walks

  2025cites this paper
• Pseudorandomness of Expander Walks via Fourier Analysis on Groups

  2025cites this paper
• Towards a Banach Space Chernoff Bound for Markov Chains via Chaining Arguments

  2025cites this paper
• Sampling from Binary Quadratic Distributions via Stochastic Localization

  2025cites this paper
• Modified Index Policies for Multi-Armed Bandits with Network-like Markovian Dependencies

  2025influential citation
• Quantum expanders and property (T) discrete quantum groups

  2025cites this paper
• Online Condensing of Unpredictable Sources via Random Walks

  2024influential citation
• The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced

  2024cites this paper
• Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate

  2024influential citation
• Optimal Load-Balanced Scalable Distributed Agreement

  2024cites this paper
• Near-Optimal Averaging Samplers and Matrix Samplers

  2024cites this paper
• Hypergraph universality via branching random walks

  2024influential citation
• Chernoff Bounds and Reverse Hypercontractivity on HDX

  2024cites this paper
• Near-Optimal Averaging Samplers

  2024cites this paper
• Derandomization with Pseudorandomness

  2024cites this paper
• Nearly-Linear Time Seeded Extractors With Short Seeds

  2024influential citation
• An Analysis of Elo Rating Systems via Markov Chains

  2024cites this paper
• Modularity and Graph Expansion

  2023cites this paper
• Pseudorandom Linear Codes are List Decodable to Capacity

  2023cites this paper
• Spectral gap of nonreversible Markov chains

  2023cites this paper
• New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms

  2023cites this paper
• Random Walks on Rotating Expanders

  2023cites this paper
• An embarrassingly parallel optimal-space cardinality estimation algorithm

  2023cites this paper
• Pseudorandomness of the Sticky Random Walk

  2023cites this paper
• EDSUCh: A robust ensemble data summarization method for effective medical diagnosis

  2022cites this paper
• A LOCAL CENTRAL LIMIT THEOREM FOR RANDOM WALKS ON EXPANDER GRAPHS

  2022influential citation
• Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification

  2022influential citation
• A local central limit theorem for random walks on expander graphs

  2022influential citation
• Pseudorandomness of expander random walks for symmetric functions and permutation branching programs

  2022cites this paper
• Expander Random Walks: The General Case and Limitations

  2021cites this paper
• Linear cover time is exponentially unlikely

  2021cites this paper
• Expander random walks: a Fourier-analytic approach

  2021cites this paper
• Support of closed walks and second eigenvalue multiplicity of graphs

  2021cites this paper
• Scalar and Matrix Chernoff Bounds from $\ell_{\infty}$-Independence

  2021cites this paper
• Random walks on hyperbolic spaces: Concentration inequalities and probabilistic Tits alternative

  2021cites this paper
• CONCENTRATION INEQUALITIES FOR RANDOM WALKS ON PROPER HYPERBOLIC SPACES

  2021cites this paper
• An Efficient Coding Theorem via Probabilistic Representations and its Applications

  2021cites this paper
• An Online Learning Approach to Computation Offloading in Dynamic Fog Networks

  2021cites this paper
• T-product Tensor Expander Chernoff Bound

  2021cites this paper
• Tensor Expander Chernoff Bounds

  2021cites this paper
• A Matrix Chernoff Bound for Markov Chains and Its Application to Co-occurrence Matrices

  2020cites this paper
• Fast Low-Space Algorithms for Subset Sum

  2020cites this paper
• Support of Closed Walks and Second Eigenvalue Multiplicity of the Normalized Adjacency Matrix

  2020cites this paper
• Sharp threshold results for computational complexity

  2020cites this paper
• Finite-time Analysis of Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards

  2020cites this paper
• The Cost of Scaling a Reliable Interconnection Topology

  2020cites this paper
• Unlinking super-linkers: the topology of epidemic response (Covid-19)

  2020cites this paper
• Concentration Bounds for Co-occurrence Matrices of Markov Chains

  2020cites this paper
• Voronoi Graph Traversal in High Dimensions with Applications to Topological Data Analysis and Piecewise Linear Interpolation

  2020cites this paper
• Chernoff Bound for High-Dimensional Expanders

  2020cites this paper
• Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards

  2020cites this paper
• The Swendsen–Wang dynamics on trees

  2020cites this paper
• Transport-information inequalities for Markov chains

  2020cites this paper
• FPRAS Approximation of the Matrix Permanent in Practice

  2020cites this paper
• Nearly Optimal Pseudorandomness From Hardness

  2020cites this paper
• Pseudobinomiality of the Sticky Random Walk

  2020cites this paper
• A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Bandits

  2020cites this paper
• Finding Large Expanders in Graphs: from Topological Minors to Induced Subgraphs

  2020cites this paper
• Imperfect gaps in Gap-ETH and PCPs

  2019cites this paper
• Concentration and Anti-concentration for Markov Chains

  2019cites this paper
• Sharp and Practical Performance Bounds for MCMC and Multiple Testing

  2019cites this paper
• Learning in Restless Multiarmed Bandits via Adaptive Arm Sequencing Rules

  2019cites this paper
• Parameterized Inapproximability for Steiner Orientation by Gap Amplification

  2019cites this paper
• Samplers and extractors for unbounded functions

  2019cites this paper
• Concentration of Markov chains with bounded moments

  2019cites this paper
• Mathematics and Computation

  2019cites this paper
• Intelligent Big Data Summarization for Rare Anomaly Detection

  2019cites this paper
• Optimal Chernoff and Hoeffding Bounds for Finite State Markov Chains

  2019cites this paper
• Junta Correlation is Testable

  2019cites this paper
• The Littlewood-Offord Problem for Markov Chains

  2019cites this paper
• Optimal Best Markovian Arm Identification with Fixed Confidence

  2019cites this paper
• On Dimension-free Tail Inequalities for Sums of Random Matrices and Applications

  2019cites this paper
• Hardness Magnification for all Sparse NP Languages

  2019influential citation
• Optimal Streaming and Tracking Distinct Elements with High Probability

  2018cites this paper
• The power of randomized algorithms: from numerical linear algebra to biological systems

  2018cites this paper
• A Hoeffding inequality for Markov chains

  2018cites this paper
• Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds

  2018cites this paper
• AN ONLINE LEARNING APPROACH TO WIRELESS COMPUTATION OFFLOADING

  2018cites this paper
• Cutoff for Random Walk on Dynamical Erd\H{o}s-R\'enyi Graph

  2018influential citation
• Cutoff for random walk on dynamical Erdős–Rényi graph

  2018influential citation
• Concentration of Measure in Matrix-Valued Dependent Settings

  2018influential citation
• Typically-correct derandomization for small time and space

  2017cites this paper
• DR AF T Ant-Inspired Density Estimation via Random Walks

  2017cites this paper
• Efficient Simulation of High Dimensional Gaussian Vectors

  2017cites this paper
• A MODERN APPROACH

  2017cites this paper
• A Sharp Tail Bound for the Expander Random Sampler

  2017influential citation
• The Complexity of a Reliable Distributed System

  2017cites this paper
• Explicit, almost optimal, epsilon-balanced codes

  2017cites this paper
• Matrix Concentration for Expander Walks

  2017cites this paper
• A matrix expander Chernoff bound

  2017cites this paper
• Intelligence of Smart Systems: Model, Bounds, and Algorithms

  2017cites this paper
• Ant-inspired density estimation via random walks

  2016cites this paper
• From graphs to keyed quantum hash functions

  2016cites this paper
• PowerWalk: Scalable Personalized PageRank via Random Walks with Vertex-Centric Decomposition

  2016cites this paper
• Function-Specific Mixing Times and Concentration Away from Equilibrium

  2016influential citation
• System intelligence: model, bounds and algorithms

  2016cites this paper
• Scaling a Reliable Distributed System

  2016cites this paper
• Explicit Resilient Functions Matching Ajtai-Linial

  2015cites this paper
• The Impact of Mobility Prediction on the Performance of P 2 P Content Discovery Protocols over Mobile Ad-Hoc Networks

  2015cites this paper
• Large Deviations and Effective Equidistribution

  2015cites this paper