Introduction - Foundations of Cryptography: Basic Tools - page 29

Exercise 4: Equivalentdefinitionof BPP .Part1:Prove that Definition 1.3.4 is robust
when

2
3

1
2 +

1
p( | x | )

is replaced by for every positive polynomial p( · ). Namely, show that

L ∈ BPP if there exists a polynomial p( · ) and a probabilistic polynomial-time machine

M such that
•

1
2 +

1
p( | x | ) , and

for every x ∈ L it holds that Pr[M(x) = 1] ≥

•

for every x

) .
Guideline: Given a probabilistic polynomial-time machine Msatisfying the foregoing con-
dition, construct a probabilistic polynomial-time machine M as follows. On input x,ma-
chine M runs O( p(

∈ L it holds that Pr[M(x) 0] ≥

1
2

1

= +

p( | x |

) 2 ) many copies of M, on the same input x, and rules by majority.
Use Chebyshev's inequality (see Section 1.2) to show that M is correct with probability
at least

| x |

2
3 .

Exercise 5: Equivalentdefinitionof BPP .Part2:Prove that Definition 1.3.4 is robust
when

3 is replaced by 1 − 2 − p( | x | ) for every positive polynomial p( · ). Namely, show that
for every L

2

∈ BPP

and every polynomial p( · ), there exists a probabilistic polynomial-

time machine M such that
•

for every x ∈ L it holds that Pr[M(x) = 1] ≥ 1 − 2 − p( | x | ) , and

• for every x ∈ L it holds that Pr[M(x) = 0] ≥ 1 − 2 − p( | x | ) .

Guideline: Similar to Exercise 4, except that you have to use a stronger probabilistic
inequality (namely, Chernoff bound; see Section 1.2).