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

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