DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.31

The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced

Authors: Amnon Ta-Shma and Ron Zadicario

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract

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.

Cite as

Amnon Ta-Shma and Ron Zadicario. The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{tashma_et_al:LIPIcs.APPROX/RANDOM.2024.31,
  author =	{Ta-Shma, Amnon and Zadicario, Ron},
  title =	{{The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{31:1--31:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.31},
  URN =		{urn:nbn:de:0030-drops-210246},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.31},
  annote =	{Keywords: Expander random walks, Expander hitting property}
}

Search Results

Documents authored by Zadicario, Ron

The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced

Abstract

Cite as

Thanks for your feedback!

Could not send message