patternMinor
Amplifying the correctness of $\mathsf{RP}$ algorithms using expander graphs
Viewed 0 times
mathsfthecorrectnessgraphsalgorithmsusingexpanderamplifying
Problem
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:
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:
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^
- 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^
Solution
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:
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}$.
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}$.
Context
StackExchange Computer Science Q#41206, answer score: 5
Revisions (0)
No revisions yet.