Content deleted Content added
Line 88:
<math>Pr[y_i^{\prime\prime} = ?] = Pr[\theta \in [0, {2\omega_i \over d}]] = {2\omega_i \over d}</math>.
The second [[Equality (mathematics)|equality]] above follows from the choice of <math>\theta</math>. The proof of '''Lemma 1''' can be also used to show <math>\mathbb{E}[2e' + s']</math> < <math>D</math> for version2 of GMD.
In the next section, we will see how to get a deterministic version of the GMD algorithm by choosing θ from a polynomially sized set as opposed to the current infinite set <math>[0, 1]</math>.
| |||