Amplifying the correctness of $\mathsf{RP}$ algorithms using expander graphs

Question

A graph $G = (V, E)$ is called an $(n, d, \varepsilon)$-expander if the graph has $n$ vertices, maximum degree $d$, and satisfies the following expansion property:

• for every subset $W\subset V$ such that $|W|\leq n/2$, $|W\cup N(W)|\ge (1+\varepsilon)|W|$

where $N(W)$ is the neighborhood of $W$ in $G$. The expansion property means, informally, that the neighborhood of $W$ is "large" when $W$ is "small". That expanders exist can be shown with the probabilistic method (see, e.g., this writeup from Ellis).

I'm trying to show that expanders can be used to amplify the success probability of one-sided Monte Carlo algorithms. In particular, given a polynomial time algorithm $A$ for a problem in RP that uses $n$ random bits and gives false negatives with probability at most $1/2$ we want to show there is a polynomial time algorithm that uses $n$ random bits and gives false negatives with probability at most $n^{-c}$ for a fixed constant $c$.

Here is the method I've been asked to analyze. We regard $A$ as a function $A(x,r)$ where $x$ is the input and $r$ is a string representing the random bits. On the input $x$ we then:

• Fix a $(2^n,d,\varepsilon)$-expander $G$ and identify its vertices with $\{0,1\}^n$
• Select a vertex $r$ of $G$ uniformly at random
• Compute the set $y_1,y_2,\ldots, y_t$ of vertices at distance at most $\delta$ from $r$ in $G$
• Say "no" if and only if $A(x,r),A(x,y_1), \ldots, A(x,y_t)$ are all "no"

What I need to show is that for $\delta = O(\log n)$ the probability of a false negative is at most $n^{-c}$.

As a side note, this is actually enough to accomplish the original goal. A result of Gabber and Galil is that there is a family of $(2^n, 5,(2 - \sqrt{3})/4)$-expanders with the additional property that the neighbors of any vertex can be enumerated in polynomial time. This means that $d$ and $\varepsilon$ can be taken uniformly in $n$, and that we can implement BFS from $r$ in polynomial time per vertex considered. Since $t\le d^{\delta + 1}$, the new algorithm runs $A$ a number of times polynomial in $n$ for $\delta = O(\log n)$ and $n$ is polynomial in the input size. Since $G$ is deterministic and does not depend on $A$, there is also clearly no new randomness.

---

Here is how I approached the problem thus far.

Let $G$ be given. Since $|V| = 2^n$, we have an identification $V \cong \{0,1\}^n$. Let $r \in \{0,1\}^n$ be chosen at random so that $r$ corresponds to a random starting point in $G$. Define a ball $B(v,\delta) = \{u \in V: d(u,v) \leq \delta\}$ where $d(u,v)$ is the length of the shortest $uv$-path. We are only interested in the number of bad balls, namely balls such that all $u\in B(v,\delta)$ result in false negatives, that is, our $\mathsf{RP}$ algorithm should accept but reject nonetheless. If we can bound above the number of bad balls by $2^n/n^c$ for some constant $c$, then we are done since an error occur if and only if the chosen vertex $y_i$ is such that $B(y_i,\delta)$ is bad.

I tried bounding the number of vertices in a bad ball using the expansion property of $G$, but I am not sure how this could help considering balls are certainly not disjoint. We also know that at most $1/2$ of the vertices will result in a false negative.

Any help would be greatly appreciated.

Answer 1

Since nobody else answered, here is what I had in mind when I made my comment. The basic idea behind the proposed amplification algorithm is that expanders are "negatively curved" in the sense that small sets in degree-bounded expanders should have a lot of their volume near the boundary. This then suggests that a ball centered in a small set should quickly "escape" with reasonable probability.

To answer a question from your comment, since the ball around a random vertex isn't a uniformly random set, we wouldn't expect a bound like $2^{-s}$ for the probability of being bad. Instead we get something that depends on $\epsilon$ and $d$ (with bigger $\epsilon$ and smaller $d$ being better if the other parameter is held fixed).

As in my comment, set $X\subset \{0,1\}^n$ to be the random strings where our RP algorithm $A(x,r)$ gives false negatives and $Y$ be the complement. Since $G$ is a $(N,d,\epsilon)$-expander with $N = 2^n$, and $|X|\le N/2$ by hypothesis, we know that:

• at least $\epsilon |X| / d$ different vertices in $X$ have a neighbor in $Y$

Notice that this already gives us something, since if we took $\delta = 1$, the improved algorithm now gives a false negative with probability only $1/2 - \epsilon/d$. The question just asks us to be a bit more ambitious.

To this end, define $$ X_i := \{r : d(r,Y) \ge i\} $$ What we just argued was that $|X_2| \le (1-\epsilon/d)|X|\le (1-\epsilon/d)N/2$. From the way we've defined $X_i$, we the neighborhood of $X_i$ is contained in $X_{i-1}$ for $i\ge 3$. This lets us replay the same argument to show that, for $i\ge 3$ we get $|X_i|\le (1-\epsilon/d)|X_{i-1}|$. By induction we then get that $|X_s|\le (1-\epsilon/d)^{s-1}N/2$.

Finally, observe that the improved algorithm fails when the chosen $r$ is in $X_{s+1}$. For $s=\Theta_{\epsilon,d}(\log n)$ this probability is $n^{-c}$.