Hardness of Approximation Between P and NP. Aviad RubinsteinЧитать онлайн книгу.

      Note that in every ϵ⁴-ANE Alice assigns a probability of at most 1 − ϵ2 to actions that are ϵ²-far from optimal. By Equation (3.2) this implies that the probability that Alice choosing a vector x that satisfies is at most ϵ².

      ■

Lemma 3.4

      In every ϵ⁴-ANE , if the first m-tuple of coordinates of is 6h-close to the binary encoding E(v) of a vertex v, then

      with probability of at least 1 − O(ϵ⁴) (where the probability is taken over ).

       Proof

      By Lemma 3.3 and the triangle inequality, with probability of at least 1 − ϵ², the first m-tuple of x is O(h)-close to E(v). Rounding to R_v(x) ∈ {0, 1}^m can at most double the distance to E(v) in each coordinate. Therefore, the Hamming distance of Rv(x) and E(v) is O(h). Hence Rv(x) is correctly decoded as Dv(x) = v, with probability of at least 1 − ϵ².

      Since do not affect , Bob’s utility from guessing vB = v, and , is at least 1 − ϵ², whereas his utility from guessing any other guess is at most ϵ². Therefore, Bob assigns probability at least 1 − ϵ4/(1 − 2ϵ²) to actions that satisfy (3.3).

      ■

      A similar lemma holds for the second m-tuple of x and the vertex w:

       Lemma 3.5

      In every ϵ⁴-ANE , if the second m-tuple of coordinates of is 6h-close to the binary encoding E(w) of a vertex w, then

      with probability of at least 1 − O(ϵ4) (where the probability is taken over ).

      Since Alice receives the correct vB and βB, we also have:

Lemma 3.6

      In every ϵ⁴-ANE , if the first m-tuple of coordinates of is 6h-close to the binary encoding E(v) of a vertex v, then

      with probability 1 − O(ϵ4) (where the probability is taken over and ).

       Proof

      Follows immediately from Lemma 3.4 and the fact that does not affect

      ■

      A similar lemma holds for the second m-tuple of x and the vertex w:

Lemma 3.7

      In every ϵ⁴-ANE , if the second m-tuple of coordinates of is 6h-close to the binary encoding E(w) of a vertex w, then

      with probability 1 − O(ϵ4) (where the probability is taken over and ).

Lemma 3.8

      In every ϵ⁴-ANE with probability 1 − O(ϵ4).

       Proof

      Follows immediately from Lemmas 3.6 and 3.7 and the “locality” condition in Proposition 3.1.

      ■

      The following corollary completes the analysis of the 2-player game.

Corollary 3.5

      In every ϵ⁴-ANE .

       Proof

      We recall that in Lemma 3.3 we have proved that

      with probability 1 − O(ϵ4). This also implies that x is, with high probability, close to its expectation:

Скачать книгу