ТОП просматриваемых книг сайта:
Hardness of Approximation Between P and NP. Aviad Rubinstein
Читать онлайн.Название Hardness of Approximation Between P and NP
Год выпуска 0
isbn 9781947487222
Автор произведения Aviad Rubinstein
Жанр Программы
Серия ACM Books
Издательство Ingram
where [·]ϵ denotes the rounding to the closest ϵ integer multiplication. x* yields a payoff of at least
Note that in every ϵ4-ANE Alice assigns a probability of at most 1 − ϵ2 to actions that are ϵ2-far from optimal. By Equation (3.2) this implies that the probability that Alice choosing a vector x that satisfies
■
Lemma 3.4
In every ϵ4-ANE
with probability of at least 1 − O(ϵ4) (where the probability is taken over
Proof
By Lemma 3.3 and the triangle inequality, with probability of at least 1 − ϵ2, the first m-tuple of x is O(h)-close to E(v). Rounding to Rv(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 − ϵ2.
Since
■
A similar lemma holds for the second m-tuple of x and the vertex w:
Lemma 3.5
In every ϵ4-ANE
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 ϵ4-ANE
with probability 1 − O(ϵ4) (where the probability is taken over
Proof
Follows immediately from Lemma 3.4 and the fact that
■
A similar lemma holds for the second m-tuple of x and the vertex w:
Lemma 3.7
In every ϵ4-ANE
with probability 1 − O(ϵ4) (where the probability is taken over
Lemma 3.8
In every ϵ4-ANE
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 ϵ4-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: