Mark Gritter (markgritter) wrote,
Mark Gritter

The Problem With Moduli

So, I'm reading "Probability and Computing: Randomized Algorithms and Probabilistic Analysis" by Michale Mitzenmacher and Eli Upfal. In the first chapter there's an exercise that asks for a randomized algorithm that works around a corrupted lookup table for a function F:[0,n)->[0,m). F is constrained such that F((x+y) mod n) = F(x)+F(y) mod m. (I believe you're supposed to show that even with 1/5th of the values compromised, that for a given z, randomly picking x and calculating F(x) + F(x-z) gives the right answer with > 50% probability.)

But... how many such functions are there? Well, the definition given is that of a homomorphism, so F(0)=0 and the rest of the function is completely determined by F(1). Thus there are only 'm' different homomorphisms.

Unfortunately I don't think this insight leads to any better solution, other than perhaps noting that there's no point in using the lookup table for x=0.
Tags: mathematics
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded