ECCC-Report TR24-118https://eccc.weizmann.ac.il/report/2024/118Comments and Revisions published for TR24-118en-usSun, 14 Jul 2024 11:38:35 +0300
Paper TR24-118
| The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced |
Ron Zadiario,
Amnon Ta-Shma
https://eccc.weizmann.ac.il/report/2024/118Numerous works have studied the probability that a length $t-1$ random walk on an expander is confined to a given rectangle $S_1 \times \ldots \times 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 $\lambda$-expanders fool \emph{Boolean},
\emph{symmetric} functions up to a $O(\lambda)$ error in \emph{total variation distance}, with \emph{no dependence on the labeling bias}.
Our techniques extend this result to cases not covered by it, e.g., to the confinement problem to $S_1 \times \ldots \times S_t$, where all sets $S_i$ either have density $\rho$ or $1-\rho$, for arbitrary $\rho$.
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\times 2$ matrices.Sun, 14 Jul 2024 11:38:35 +0300https://eccc.weizmann.ac.il/report/2024/118