This property is often known as “linear\". Such a function can be stored by usin

Question

This property is often known as “linear". Such a function can be stored by using a table of size n, e.g. the table is the array [F(0), F(1)…..F(n - 1)]. Suppose someone stores such a table inside a device and then sends that device to you. The specification of the device allows you to query some index “i” and returns F(i). However, the device was somewhat damaged by the time of delivery: 1/5 of the tables were corrupted, and you don't know which parts were corrupted. If an entry j is corrupted, the device will still return some value F’(j) to you upon query, but F’(j) might not be the original value F(j). Also, the value F’(j) is a normal value in {0,1,2, …m - 1}, and it will not say “I am corrupted".

Problem: 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 can query the device on whatever inputs in {0,1,2, …n - 1}, but it should query as fewer as possible. Also, your algorithm should work for every z no matter which parts of the tables were corrupted. Consider an algorithm that queries the device on the input z and outputs the answer from the device. This algorithm does not work, because if it does not work for every z. If the entry at z is corrupted, then the algorithm will output something wrong. Suppose you are allowed to repeat the initial algorithm three times, what should you do? What is the probability that your enhanced algorithm returns the correct answer?

Explanation / Answer

We have a function F : f0; : : : ; n ¡ 1g ! f0; : : : ;m ¡ 1g. We know that, for any x and y with 0 · x; y · n ¡ 1, F((x + y) mod n) = (F(x) + F(y)) mod m.

The values of F are stored in a lookup table so that we can evaluate any F(x) easily and correctly.

Describe a simple randomized algorithm that, given any input z, outputs the correct value F(z) with probability at least 1/2. Note that your algorithm needs to work for every value of z.

Ans: We pick an x, uniformly at random, from [0; n - 1].

Then, we compute y =z-x mod n.

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

Pr (the output F(z) is correct)

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

= 1 - Pr (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.

Suppose you can repeat your initial algorithm three times. Can you improve the probability of returning the correct value?

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.

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.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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