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