Problem 3: (30 points) We have a function F: {0,..,n-1 } {0, ,m-1). We know that

Question

Problem 3: (30 points) We have a function F: {0,..,n-1 } {0, ,m-1). We know that, for 0 mod n)- (F(x)+F) 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. x, y n-1, FOx + y) Describe a simple randomized algorithm that, given an input z, outputs a value that equals Fe) 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 I allow you 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?

Explanation / Answer

Answer of Part 1)

Randomized algorithm:

Let us pick an x, uniformly at random, from [0, n 1].

Then, we compute y = z x mod n.

Then we output (F(x) +F(y)) mod m as our computed value for F(z).

Then, we have the following:

Probability (the output F(z) is correct)

Probability (F(x) and F(y) are not modified)

= 1 Probability (F(x) or F(y) are modified)

1 (Pr (F(x) is modified) + Pr (F(y) is modified))

1 (1/5 + 1/5) = 3/5.

whre pr is probability

Answer for part 2):

If we can repeat the algorithm three times, we pick three values (with replacement)

of y1, y2, y3 as our y value, and compute the corresponding values of F(z1), F(z2), F(z3). If

at least two of the F(z) values are equal, we output such value. Otherwise, we output any

one of these values. Then, we have the following:

Pr (the output F(z) is correct)

Pr (at least two of the F(z1), F(z2), F(z3) are correct)

= Pr (exactly two of the F(z1), F(z2), F(z3) are correct)

+Pr (all F(z1), F(z2), F(z3) are correct)

3 × 3/5 × 3/5 × 2/5 + (3/5)^3

54/125 + 27/125 = 81/125.

where pr is probabaility

So we have better probability if we repeat three times.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.