Exercise 4 (4 pts). Let A be a two-sided error Monte Carlo algorithm that decides a language L so that either answer is correct with probability 0.6. Answer the following questions (1 pt for each correct answer):

3. Suppose that x is a yes instance and you run A on x for 100 times. What is the probability that the number of yes answers returned by A is less than 30? Hint. Use the Chernoff-bound inequality Pr[|X pk| > pk] < e 2 4 pk with p = 0.6 and k = 100. Find the largest value of such that if X < 30 then |Xpk| > pk. Using these , p, k, find the Chernoff bound for the required probability.

4. Explain how you can use A (as a subroutine) to decide the same language so that either answer is correct with probability 0.9. Hint. Use the Amplification Lemma with k = 8 ln(1/) 2 .