A family of hash functions is k-independent if selecting a function at random guarantees that the hash codes of any designated k keys are independent random variables. This allows for good average case performance in randomized algorithms or data structures, even when the input data is chosen by an adversary. Many k-independent families have been proposed to balance the degree of independence and the efficiency of evaluating the hash function.
UC Berkeley
Fall 2021
This course explores the role of randomness in computation and pseudorandomness, focusing on the applications in error-correcting codes, expander graphs, randomness extractors, and pseudo-random generators. The course will also address the question of derandomization of small-space computation. Prerequisites are unspecified, but the course content suggests a high level of expertise.
No concepts data
+ 26 more concepts