Solution for Exercise 1.18

Exercise 1.18 )       

We have a function F : {0,...,n − 1} → {0,...,m − 1}. We know that , for 0 ≤ x, y ≤ n−1, F((x+y) mod n)=(F(x)+F(y)) mod m. The only way we have for evaluating F is to use a lookup table that stores the values of F. Unfortunately, an Evil Adversary has changed the value of 1/5 of the table entries when we were not looking.

Describe a simple randomized algorithm that, given an input z, outputs a value that equals F(z) with probability at least 1/2. Your algorithm should work for every value of z, regardless of what values the Adversary changed. Your algorithm should use as few lookups and as little computation as possible.

Suppose you are allowed to repeat your initial algorithm three times. What should you do in this case, and what is the probability that your enhanced algorithm returns the correct answer?

 

 

 

 

 

Solution:
1. [3points]

Choose x uniformly from {0,...,n−1} and let y = z−x mod n.

Then output the value F(z) as F (z) = F (x) + F (y) mod m

Note that x and y = z−x are both a uniformly random number in the range {0, . . . , n−1}, but they are not independent. So, we have Pr[“F(x) is corrupted”] = Pr[“F(y) is corrupted”] = 1/5. Then by union bound

P [error] = P [“F (x) is corrupted” ∪ “F (y) is corrupted”] ≤ 2/5

 

 

 

correct with probability at least ( 5 ) = 125 , so the probability of a correct answer is at least 125 .