General Multi-Forking Lemma with Oracle Access
Here we state and prove an extended version of the forking lemma of [PS00]. Our forking lemma analyzes the output behavior of an algorithm when run multiple times on related inputs, instead of when only run twice, while also providing it with oracle access to a deterministic algorithm .
Fix an integer and a set of size Let be a randomized algorithm that has oracle access to some deterministic algorithm , where on input , , algorithm returns a pair; the first element is an integer in the range and the second element is what we refer to as a side output. Let be a randomized algorithm called the input generator. The accepting probability of , denoted , is defined as the probability that in the experiment below:
For a positive integer , the forking algorithm associated to is a randomized oracle algorithm that takes input and proceeds as below, where denotes an arbitrary set of strings. Let
Then,
where is some universal positive valued function that only depends on the value .
.
For any input , denote as the probability that in the following experiment:
Also, let We claim that there exists some universal positive valued function such that for all ,
By taking the expectation of over and using the fact (which follows from Jensen's inequality), we obtain Eq. (1). Therefore, to prove the claim, we must prove Eq. (2).
Now, for any input , with the probabilities taken over the coin tosses of is equivalent to the following.
Here, we can rewrite , where are functions that only depend on . Since , we can always upper bound the right hand side by using some positive valued function that only depends on , where for example, we can use Here, note that is some universal function that depends neither on nor . Therefore, we can further rewrite the inequality as follows:
Hence, it remains to show that for all Let denote the set from which draws its random coins. For each , let be defined by setting to
for all and Here, regard as a random variable over the uniform distribution on its domain.
Here Eq. (3) follows from independence of and for , Eq. (4) follows from the fact that once are fixed and Eq. (5) follows from Jensen's inequality where we use the fact that is a convex function. Finally, using Holder's inequality, we obtain
This completes the proof of Eq. (1), hence concluding our claim.
As can be checked from the proof, we can set the function so that in case , we have . Therefore, by setting the deterministic oracle to be an oracle that outputs nothing, the above lemma implies the general forking lemma of [BN06].