# Deterministic algorithms for computational distance between distributions

Computational distance between sequences of distributions $$\{X_i\}_{i \in \mathbb{N}}$$ and $$\{Y_i\}_{i \in \mathbb{N}}$$ can be defined as the maximum, over all probabilistic polynomial time algorithms $$A$$, of $$\left|\underset{x \sim X_{n}}{\mathsf{Pr}}(A(x) = 1) - \underset{x \sim Y_{n}}{\mathsf{Pr}}(A(x) = 1)\right|,$$

for each $$n \in \mathbb{N}$$. We can, very similarly, define computational indistinguishability to be when the computational distance is a negligible function of $$n$$. Here is my question: can we use a deterministic polynomial-time algorithm in place of a probabilistic one without loss of generality? Can we say that the maximum computational distance is achieved by a deterministic algorithm? Will this algorithm be non-uniform?

• Does the following help? Every randomized algorithm is a distribution over deterministic algorithms. Nov 25 '20 at 19:42
• Yes, I think it helps. Just for a quick sanity check, the answers are: yes, we can use a deterministic-polynomial time algorithm without losing generality; the maximum is achieved by one such algorithm; the algorithm will be non-uniform (a particular sequence of the random bits need to be hard-coded in the input); right? Nov 26 '20 at 4:42
• Can we have deterministic algorithms that have other forms of non-uniformity, without loss of generality in the definition? For example, the ability to sample from either $X_{n}$ or $Y_{n}$ (ie, the algorithm will be deterministic given the samples)? Nov 26 '20 at 4:49

Every randomized algorithm $$A(x)$$ can be expressed as a deterministic algorithm $$A(x;r)$$ where $$r$$ is randomly chosen. Now what can you say about the value of that absolute difference for different choices of $$r$$? What would you like to be able to say about it?