(Strongly) Replicable Distribution Testers imply High Probability Distribution Testers

We study connections between the sample cost of replicability, which requires an algorithm to produce consistent outputs in different runs, and the sample complexity in the high success probability regime for distribution testing algorithms. Specifically, we consider a stronger notion of replicability, which we term as strong replicability, and show that any $\rho$-strongly-replicable testing algorithm can be converted in a blackbox manner to a tester with at most $\exp (-\tilde{\Omega }({\rho }^{-2}))$ failure probability under the same sample budget. Our conversion is optimal for many natural testers. As applications of our conversion theorem, we obtain tight sample lower bounds for strongly replicable testers for coin bias and closeness testing.