<p>Doesn't van Melkebeek's lecture notes already give a <span class="math-container">$O(1/\delta)$</span> bound? The bound there is <span class="math-container">$\lambda$</span> at most <span class="math-container">$O(\sqrt{\delta})$</span> and we can get <span class="math-container">$\lambda = O(1/\sqrt{d})$</span> using existing constructions. </p>

<p>In Dwork's lecture notes as well, the condition required is that the expansion be <span class="math-container">$C/\delta$</span> for some constant <span class="math-container">$C$</span> (looking at a points in distance c is essentially using powering to improve expansion). Which again can be obtained with degree <span class="math-container">$O(1/\delta)$</span>.</p>

<p>Perhaps there is a lower bound of <span class="math-container">$\Omega(1/\delta)$</span> on number of runs required. </p>

CC BY-SA 4.0
2019-06-18T14:40:44.660Z
I see -- let me rephrase it to confirm I get this right. Letting $\alpha>0$ being the original error probability, if we have a spectral degree-$d$ expander on $R=2^r$ nodes with second eigenvalue $\lambda \leq \sqrt{\delta}\cdot C_\alpha$ (where $C_\alpha$ is explicit, different for RP and BPP) then we get a blowup in running time of $d$. So if we have a family of explicit $(N,d)$-expanders with $\lambda \leq C/\sqrt{d}$ for all $N$, $d$, all we need is $d = O_\alpha(1/\delta)$ for the bound to be satisfied.
Clement C.
CC BY-SA 4.0
2019-06-19T04:46:43.143Z
For instance, arbitrarily large Ramanujan graphs are known to exist (constructively) for any degree $d$ such that $d-1$ is a prime power. But do we have explicit constructions of graphs with $\lambda = O(1/\sqrt{d})$ for *all* $n$ (or, let's say, for all $n$ which is a power of two)? (I'm not knowledgeable enough on that, and the only result of that sort I could find is Balu-Linial's construction which gives $O(\sqrt{(\log^3 d)/d})$ and is not strongly explicit).
Clement C.
CC BY-SA 4.0
2019-06-18T03:08:36.820Z
2019-06-18T03:08:36.820Z
guest
<p>Assume one has a randomized (BPP) algorithm <span class="math-container">$A$</span> using <span class="math-container">$r$</span> bits of randomness. Natural ways to amplify its probability of success to <span class="math-container">$1-\delta$</span>, for any chosen <span class="math-container">$\delta&gt;0$</span>, are </p>

<ul>
<li>Independent runs + majority vote: run <span class="math-container">$A$</span> independently <span class="math-container">$T=\Theta(\log(1/\delta)$</span> times, and take the majority vote of the outputs. This requires <span class="math-container">$rT =\Theta(r\log(1/\delta))$</span> bits of randomness, and blows up the running time by a <span class="math-container">$T=\Theta(\log(1/\delta))$</span> factor.</li>
<li>Pairwise independent runs + Chebyshev: run <span class="math-container">$A$</span> "pairwise-independently" <span class="math-container">$T=\Theta(1/\delta)$</span> times, and compare to a threshold This requires <span class="math-container">$rT =\Theta(r/\delta)$</span> bits of randomness, and blows up the running time by a <span class="math-container">$T=\Theta(1/\delta)$</span> factor.</li>
</ul>

<p>Karp, Pippenger, and Sipser [1] <em>(apparently; I couldn't get my hands on the paper itself, it's a second-hand account)</em> provided alternative approaches based on strong regular expanders: essentially, see the <span class="math-container">$2^r$</span> nodes of the expander as the random seeds. Pick a random node of the expander using the <span class="math-container">$r$</span> random bits, and then</p>

<ul>
<li><p>do a short random walk of length <span class="math-container">$T=\Theta(\log(1/\delta))$</span> from there, and run <span class="math-container">$A$</span> on the <span class="math-container">$T$</span> seeds corresponding to nodes on the path, before taking a majority vote. This requires <span class="math-container">$r+T = r+\Theta(\log(1/\delta))$</span> bits of randomness, and blows up the running time by a <span class="math-container">$T=\Theta(\log(1/\delta))$</span> factor.</p></li>
<li><p>run <span class="math-container">$A$</span> on all neighbors of the current node (or, more generally, all nodes within a distance <span class="math-container">$c$</span> of the current node) before taking a majority vote. This requires <span class="math-container">$r$</span> bits of randomness, and blows up the running time by a <span class="math-container">$T=d$</span> factor, where <span class="math-container">$d$</span> is the degree (or <span class="math-container">$d^c$</span> for distance-<span class="math-container">$c$</span> neighborhood. Setting up the parameters well, this ends up costing <span class="math-container">$T=\operatorname{poly}(1/\delta)$</span> here.</p></li>
</ul>

<blockquote>
  <p>I am interested in the last bullet, which corresponds to <em>deterministic</em> error reduction. Has there been any improvement following [1], reducing the dependence of <span class="math-container">$T$</span> on <span class="math-container">$\delta$</span>? What is the current best achievable -- <span class="math-container">$1/\delta^\gamma$</span> for which <span class="math-container">$\gamma &gt; 1$</span>? <span class="math-container">$\gamma &gt; 0$</span>? (For <span class="math-container">$\textsf{BPP}$</span>? For <span class="math-container">$\textsf{RP}$</span>?)</p>
</blockquote>

<p><strong>Note:</strong> I'm also (very) interested in <span class="math-container">$\textsf{RP}$</span> instead of <span class="math-container">$\textsf{BPP}$</span>. As introduced in [2], the relevant construction then is no longer expanders, but <em>dispersers</em> (see e.g., these <a href="https://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Lecture2.pdf" rel="nofollow noreferrer">lecture notes</a> by Ta-Shma, esp. Table 3). I couldn't find the corresponding bounds for deterministic (not a single more random bit than the allowed <span class="math-container">$r$</span>) amplification, however, nor (more importantly) what the state-of-the-art explicit disperser constructions for the relevant range of parameters are.</p>

<hr>

<p>[1] Karp, R., Pippenger, N. and Sipser, M., 1985. <em>A time-randomness tradeoff</em>. In AMS Conference on Probabilistic Computational Complexity (Vol. 111). </p>

<p>[2] Cohen, A. and Wigderson, A., 1989, October. <em>Dispersers, deterministic amplification, and weak random sources.</em> In 30th Annual Symposium on Foundations of Computer Science (pp. 14-19). IEEE.</p>

CC BY-SA 4.0
2019-06-15T19:05:55.553Z
My understanding is the following (mostly on the aforementioned lecture notes of [Ta-Shma](https://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Lecture2.pdf), those of [van Melkebeek](http://pages.cs.wisc.edu/~dieter/Courses/2011f-CS710/Scribes/PDF/lecture16.pdf), and those by [Cynthia Dwork](http://www.tcs.tifr.res.in/~prahladh/teaching/05spring/lectures/lec1.pdf). As far as I can tell, dispersers are great to amplify exponentially *given few more random bits*, but not if there are 0 extra bits of randomness.
Clement C.
CC BY-SA 4.0
2019-06-15T19:10:02.523Z
(if one is willing do use these few extra bits, then Ta-Shma's lecture has a very handing set of summarizing tables) . With no extra randomness,, the expander-based BPP/RP approach looks like the only one (see van Melkebeek's notes for BPP, Dwork's for the RP variant,: both are very similar and based on the paper [1], of which I couldn't find a direct pdf). 
 None appears to give an explicit bound on the degree of the polynomial in the $\mathrm{poly}(1/\delta)$, as it depends on the degree and expansion of the expander graph.
Clement C.
CC BY-SA 4.0
2019-06-15T19:10:52.217Z
It will be at least linear in $1/\delta$: but what will it be for the (current) best known constructions of expander graphs? Actually, even for probabilistic constructions?
Clement C.
CC BY-SA 4.0
2019-06-17T21:19:05.793Z
Also relevant (but does not answer the specific question): Section 3.5.4, and Section 4 (Problem 4.6) of Salil Vadhan's *[Pseudorandomness](https://people.seas.harvard.edu/~salil/pseudorandomness/)*.
Clement C.
<reference-request><randomness><pseudorandomness><expanders>
Deterministic error reduction, state-of-the-art?
Clement C.
# Deterministic error reduction, state-of-the-art?

(Asked by: username_0 on 2019-06-11)

Assume one has a randomized (BPP) algorithm $A$ using $r$ bits of randomness. Natural ways to amplify its probability of success to $1-\delta$, for any chosen $\delta>0$, are

* Independent runs + majority vote: run $A$ independently $T=\Theta(\log(1/\delta)$ times, and take the majority vote of the outputs. This requires $rT =\Theta(r\log(1/\delta))$ bits of randomness, and blows up the running time by a $T=\Theta(\log(1/\delta))$ factor.
* Pairwise independent runs + Chebyshev: run $A$ "pairwise-independently" $T=\Theta(1/\delta)$ times, and compare to a threshold This requires $rT =\Theta(r/\delta)$ bits of randomness, and blows up the running time by a $T=\Theta(1/\delta)$ factor.

Karp, Pippenger, and Sipser [1] *(apparently; I couldn't get my hands on the paper itself, it's a second-hand account)* provided alternative approaches based on strong regular expanders: essentially, see the $2^r$ nodes of the expander as the random seeds. Pick a random node of the expander using the $r$ random bits, and then

* do a short random walk of length $T=\Theta(\log(1/\delta))$ from there, and run $A$ on the $T$ seeds corresponding to nodes on the path, before taking a majority vote. This requires $r+T = r+\Theta(\log(1/\delta))$ bits of randomness, and blows up the running time by a $T=\Theta(\log(1/\delta))$ factor.
* run $A$ on all neighbors of the current node (or, more generally, all nodes within a distance $c$ of the current node) before taking a majority vote. This requires $r$ bits of randomness, and blows up the running time by a $T=d$ factor, where $d$ is the degree (or $d^c$ for distance-$c$ neighborhood. Setting up the parameters well, this ends up costing $T=\operatorname{poly}(1/\delta)$ here.

> I am interested in the last bullet, which corresponds to *deterministic* error reduction. Has there been any improvement following [1], reducing the dependence of $T$ on $\delta$? What is the current best achievable -- $1/\delta^\gamma$ for which $\gamma > 1$? $\gamma > 0$? (For $\textsf{BPP}$? For $\textsf{RP}$?)

**Note:** I'm also (very) interested in $\textsf{RP}$ instead of $\textsf{BPP}$. As introduced in [2], the relevant construction then is no longer expanders, but *dispersers* (see e.g., these [lecture notes](https://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Lecture2.pdf) by Ta-Shma, esp. Table 3). I couldn't find the corresponding bounds for deterministic (not a single more random bit than the allowed $r$) amplification, however, nor (more importantly) what the state-of-the-art explicit disperser constructions for the relevant range of parameters are.

---

[1] Karp, R., Pippenger, N. and Sipser, M., 1985. *A time-randomness tradeoff*. In AMS Conference on Probabilistic Computational Complexity (Vol. 111).

[2] Cohen, A. and Wigderson, A., 1989, October. *Dispersers, deterministic amplification, and weak random sources.* In 30th Annual Symposium on Foundations of Computer Science (pp. 14-19). IEEE.

**Tags:** reference-request, randomness, pseudorandomness, expanders
> **Comments:**
> **username_0**: My understanding is the following (mostly on the aforementioned lecture notes of [Ta-Shma](https://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Lecture2.pdf), those of [van Melkebeek](http://pages.cs.wisc.edu/~dieter/Courses/2011f-CS710/Scribes/PDF/lecture16.pdf), and those by [Cynthia Dwork](http://www.tcs.tifr.res.in/~prahladh/teaching/05spring/lectures/lec1.pdf). As far as I can tell, dispersers are great to amplify exponentially *given few more random bits*, but not if there are 0 extra bits of randomness.  
> **username_0**: (if one is willing do use these few extra bits, then Ta-Shma's lecture has a very handing set of summarizing tables) . With no extra randomness,, the expander-based BPP/RP approach looks like the only one (see van Melkebeek's notes for BPP, Dwork's for the RP variant,: both are very similar and based on the paper [1], of which I couldn't find a direct pdf).   None appears to give an explicit bound on the degree of the polynomial in the $\mathrm{poly}(1/\delta)$, as it depends on the degree and expansion of the expander graph.  
> **username_0**: It will be at least linear in $1/\delta$: but what will it be for the (current) best known constructions of expander graphs? Actually, even for probabilistic constructions?  
> **username_0**: Also relevant (but does not answer the specific question): Section 3.5.4, and Section 4 (Problem 4.6) of Salil Vadhan's *[Pseudorandomness](https://people.seas.harvard.edu/~salil/pseudorandomness/)*.  

---

## 1 answers

### Answer by username_1 on 2019-06-18. Score: 3 | Accepted answer

Doesn't van Melkebeek's lecture notes already give a $O(1/\delta)$ bound? The bound there is $\lambda$ at most $O(\sqrt{\delta})$ and we can get $\lambda = O(1/\sqrt{d})$ using existing constructions.

In Dwork's lecture notes as well, the condition required is that the expansion be $C/\delta$ for some constant $C$ (looking at a points in distance c is essentially using powering to improve expansion). Which again can be obtained with degree $O(1/\delta)$.

Perhaps there is a lower bound of $\Omega(1/\delta)$ on number of runs required.

> **Comments:**
> **username_0**: I see -- let me rephrase it to confirm I get this right. Letting $\alpha>0$ being the original error probability, if we have a spectral degree-$d$ expander on $R=2^r$ nodes with second eigenvalue $\lambda \leq \sqrt{\delta}\cdot C_\alpha$ (where $C_\alpha$ is explicit, different for RP and BPP) then we get a blowup in running time of $d$. So if we have a family of explicit $(N,d)$-expanders with $\lambda \leq C/\sqrt{d}$ for all $N$, $d$, all we need is $d = O_\alpha(1/\delta)$ for the bound to be satisfied.  
> **username_0**: For instance, arbitrarily large Ramanujan graphs are known to exist (constructively) for any degree $d$ such that $d-1$ is a prime power. But do we have explicit constructions of graphs with $\lambda = O(1/\sqrt{d})$ for *all* $n$ (or, let's say, for all $n$ which is a power of two)? (I'm not knowledgeable enough on that, and the only result of that sort I could find is Balu-Linial's construction which gives $O(\sqrt{(\log^3 d)/d})$ and is not strongly explicit).  

---

