1
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Does the following help? Every randomized algorithm is a distribution over deterministic algorithms. $\endgroup$ Nov 25 '20 at 19:42
  • $\begingroup$ 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? $\endgroup$
    – BlackHat18
    Nov 26 '20 at 4:42
  • $\begingroup$ 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)? $\endgroup$
    – BlackHat18
    Nov 26 '20 at 4:49
1
$\begingroup$

Hint:

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?

$\endgroup$

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.