Question

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. 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?

Answer 1

Answer: part 1: Randomized algorithm otwo Let us picla an x, uni tormly at random, From coin-i] Then, we compute y=Z-x modn. Then we owl put (F(X) + Fcy)] mod mas our compiled value for f(z) Then, we have the following: poobability (the output F(z) is correct) > probability (F(x) and Fly) are not modibied) probability (FCA) 06 Fy)) are modified 31-(P• (FC) is modi ti ed) + P Fcy) is modified Z !-(15+10) by (out. Word =|- 5 TL 315 ba Where po is probability

- parta: JF We can repeat the algorithm three times, we pick thre e value cwith replacement). Of Y, Yz. 43 as our y valve, and compuele the corresponding values of FCZı), F(22), FCZ3). Jf at least two of the F(z) valug are equal we output such value otherwise, we out put any one of these valus. Then, we have the following: Po ( the output Ecz) is correct) 2 px (at least two of the F(Z1), EC22), F(23) are correct). B (exactly two of the F(Zı), FC72), FC IF(23) are correct). + Do Call FCZ!). ECZ2), F&3) are correct) > 3x 3/5 315x215 +(37053 354 /125 + 27/125 = 81/125. Wal here po is probability So we have better probability if we repeat three times.