mardi 24 novembre 2020

How to use O(log n) mutually independent random bits to generate n pairwise independent random bits

We motivated this problem by “saving space”, yet then, we went ahead and stored n pairwise independent random bits ξi . That pretty much defeats the purpose. Show how to use O(log n) mutually independent random bits to generate n pairwise independent random bits. (Thus, all you really need to store are those O(log n) bits.)




Aucun commentaire:

Enregistrer un commentaire