Forking Lemma - Statement of The Lemma

Statement of The Lemma

The generalized version of the lemma is stated as follows. Let A be a probabilistic algorithm, with inputs (x, h1, ..., hq; r) that outputs a pair (J, y), where r refers to the random tape of A (that is, the random choices A will make). Suppose further that IG is a probability distribution from which x is drawn, and that H is a set of size h from which each of the hi values are drawn according to the uniform distribution. Let acc be the probability that on inputs distributed as described, the J output by A is greater than or equal to 1.

We can then define a "forking algorithm" FA that proceeds as follows, on input x:

  1. Pick a random tape r for A.
  2. Pick h1, ..., hq uniformly from H.
  3. Run A on input (x, h1, ..., hq; r) to produce (J, y).
  4. If J = 0, then return (0, 0, 0).
  5. Pick h'J, ..., h'q uniformly from H.
  6. Run A on input (x, h1, ..., hJ−1, h'J, ..., h'q; r) to produce (J', y').
  7. If J' = J and hJh'J then return (1, y, y'), otherwise, return (0, 0, 0).

Let frk be the probability that FA outputs a triple starting with 1, given an input x chosen randomly from IG. Then

Read more about this topic:  Forking Lemma

Famous quotes containing the words statement of and/or statement:

    Truth is used to vitalize a statement rather than devitalize it. Truth implies more than a simple statement of fact. “I don’t have any whisky,” may be a fact but it is not a truth.
    William Burroughs (b. 1914)

    The new statement is always hated by the old, and, to those dwelling in the old, comes like an abyss of skepticism.
    Ralph Waldo Emerson (1803–1882)