I do have a seemingly fundamental question that I somehow struggle to intuitively make sense of.

Setting: Let us consider a randomized algorithm $R$ that has $t$ steps. In each step, it is fed with random input data $(s_1,...s_t)$, where each $s_i$ is drawn from some exponentially large set (uniformly random). Moreover, after each $s_i$ the algorithm $R$ outputs response $v_i$ with some properties that can efficiently be verified. Assume the algorithm $R$ has a non-negligible probability $\varepsilon$ to finish successfully given these random inputs. Also, by construction, assume that we must have that there is at least one so-called excellent response among all the $t$ responses. Excellence can also be tested efficiently. For notational purposes, we may assume that in our successful run the response $v_j$ with $j\in[1;t]$ is excellent.

So far so good.

Rewinding and Sending New Inputs: We now step-wisely generate $r$ uniformly random data elements $u_1,\dots , u_r$. For each $u_i$, we re-run/re-start the algorithm $R$ with the same randomness (re-wind it) and try to send the overall sequence $(s_1,...,s_{j-1},t_i)$ to R. This means that the first $j-1$ inputs stay the same, only the last one is one of our new $u_i$. We analyze if $R$ outputs a proper response $w_i$ and if so we check if it is excellent.

How large must $r$ be to obtain $p$ excellent responses (in terms of $\varepsilon$, $t$, $p$)?

I would love to use the following powerful core argument but have the suspicion, that things are actually much more complicated: Intuitively, I would like to argue that the probability of $R$ behaving differently after receiving $u_i$ is small in contrast to $R$'s behaviour after receiving the original $s_j$, since both $u_i$ and $s_j$ are equally distributed.
This should intuitively lead to an upper bound of the event

$$ Pr[R \text{ does requested behaviour on } s_j] . Pr[R \text{ does not do requested behaviour on } u_i] = Pr[R \text{ does requested behaviour on } s_j].(1-Pr[R \text{ does requested behaviour on } u_i]) = Pr[R \text{ does requested behaviour on } s_j].(1-Pr[R \text{ does requested behaviour on } s_j]) = \frac{1}{4} $$

This can serve to lower bound the probability that in both runs $R$ does the requested behaviour. So we expect that after 4 trials we should obtain the next excellent element and $r = 4p$. This is neat as it is independent of $t$ and $\varepsilon$. But the probability is of course conditioned on the fact that $(s_1,\dots ,s_t)$ makes $R$ accept in the first place.

It would be nice to have a blueprint of how to make this argument work or to see when it can be applied -- or when it fails fundamentally.

Remarks: Please note that I am indeed concerned with drawing uniformly random data inputs. I see that drawing distinct data inputs would complicate the issue. I find this case also interesting but not necessary.

Also, although I would love to keep the requirement that $u_i$ should substitute $s_j$ (with excellent $v_j$) for simplicity, I am ok with giving up the condition if fundamentally required. This means that in this case, we could draw a random index $j$ such that $u_i$ is sent to $R$ in the rewound run instead of $s_j$. However, the response to $u_i$ still needs to be excellent.

  • $\begingroup$ I'm trying to work on your problem, however, I have a few questions. First, you said "Assume the algorithm R has a non-negligible probability ε to finish successfully" isn't this to finish unsuccessfully instead of successfully? $\endgroup$
    – ARK1375
    Aug 31, 2022 at 8:52
  • $\begingroup$ I am interested in an algorithm R that when given $(s_1,...s_t)$, each input random, has success probability $\epsilon$ that is non-negligible i.e. $1/poly$ for some $poly$. Intuitively, this means that $R$ works efficiently in case it also has polynomial runtime. For our purpose, it says that for each $s_i$, $R$ will output proper $v_i$, and there is at least one excellent $v_j$. Given this assumption, I would like to lower-bound the size of $r$. $\endgroup$
    – user153219
    Aug 31, 2022 at 14:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.