# 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>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 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.

• My understanding is the following (mostly on the aforementioned lecture notes of Ta-Shma, those of van Melkebeek, and those by Cynthia Dwork. 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. Jun 15, 2019 at 19:05
• (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. Jun 15, 2019 at 19:10
• 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? Jun 15, 2019 at 19:10
• Also relevant (but does not answer the specific question): Section 3.5.4, and Section 4 (Problem 4.6) of Salil Vadhan's Pseudorandomness. Jun 17, 2019 at 21:19

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.
• 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. Jun 18, 2019 at 14:40
• 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). Jun 19, 2019 at 4:46