Deterministic error reduction, state-of-the-art? 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&gt;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 &gt; 1$? $\gamma &gt; 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 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.
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.