2026-07-22T08:35:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21024 2024-09-16T06:02:38Z ddc:004 open_access

The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced Ta-Shma, Amnon Zadicario, Ron Expander random walks Expander hitting property Numerous works have studied the probability that a length t-1 random walk on an expander is confined to a given rectangle S_1 × … × S_t, providing both upper and lower bounds for this probability. However, when the densities of the sets S_i may depend on the walk length (e.g., when all set are equal and the density is 1-1/t), the currently best known upper and lower bounds are very far from each other. We give an improved confinement lower bound that almost matches the upper bound. We also study the more general question, of how well random walks fool various classes of test functions. Recently, Golowich and Vadhan proved that random walks on λ-expanders fool Boolean, symmetric functions up to a O(λ) error in total variation distance, with no dependence on the labeling bias. Our techniques extend this result to cases not covered by it, e.g., to functions testing confinement to S_1 × … × S_t, where each set S_i either has density ρ or 1-ρ, for arbitrary ρ. Technique-wise, we extend Beck’s framework for analyzing what is often referred to as the "flow" of linear operators, reducing it to bounding the entries of a product of 2×2 matrices. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amnon Ta-Shma and Ron Zadicario 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.31 urn:nbn:de:0030-drops-210246 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.31 eng https://creativecommons.org/licenses/by/4.0/legalcode