12
$\begingroup$

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.

$\endgroup$

This question had a bounty worth +50 reputation from Clement C. that ended 15 hours ago. Grace period ends in 8 hours

The question is widely applicable to a large audience. A detailed canonical answer is required to address all the concerns.

  • $\begingroup$ 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. $\endgroup$ – Clement C. Jun 15 at 19:05
  • $\begingroup$ (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. $\endgroup$ – Clement C. Jun 15 at 19:10
  • $\begingroup$ 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? $\endgroup$ – Clement C. Jun 15 at 19:10
  • $\begingroup$ Also relevant (but does not answer the specific question): Section 3.5.4, and Section 4 (Problem 4.6) of Salil Vadhan's Pseudorandomness. $\endgroup$ – Clement C. Jun 17 at 21:19
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Clement C. Jun 18 at 14:40
  • $\begingroup$ 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). $\endgroup$ – Clement C. Jun 19 at 4:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.