vendredi 19 mai 2023

Create a randomized function with restriction on communication size

I need to create a randomized function between two participants, 1 and 2. The two participants have both n bit sized strings, and they want to determine whatever they have the same strings. 1 and 2 can communicate using only log(n) bits. The probability of error should be at most 1/3, but the function can be run multiple time and take a "majority vote" for which conclusion appeared in most of the runs, in order to decrease the error probability.

I have tried multiple ideas - for example, using a hash function where the "random" part in the algorithm is that 1 chose a random hash method each run and communicate it to 2 using the log(n) bits. But it's either that I can't prove that the probability of error is at most 1/3 or that I need to use more then log(n) bits, do you have a general idea how to achieve it ?




Aucun commentaire:

Enregistrer un commentaire