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 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.