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 hJ ≠ h'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 the, statement of and/or statement:

    “It is commonplace that a problem stated is well on its way to solution, for statement of the nature of a problem signifies that the underlying quality is being transformed into determinate distinctions of terms and relations or has become an object of articulate thought.”
    —John Dewey (1859–1952)

    “Most personal correspondence of today consists of letters the first half of which are given over to an indexed statement of why the writer hasn’t written before, followed by one paragraph of small talk, with the remainder devoted to reasons why it is imperative that the letter be brought to a close.”
    —Robert Benchley (1889–1945)

    “One is apt to be discouraged by the frequency with which Mr. Hardy has persuaded himself that a macabre subject is a poem in itself; that, if there be enough of death and the tomb in one’s theme, it needs no translation into art, the bold statement of it being sufficient.”
    —Rebecca West (1892–1983)