• Overview
• Details
• Exercises

Derandomization studies how to reduce or eliminate randomness in algorithms while preserving guarantees. Tools include limited independence, pairwise-independent hash families, expander walks, and pseudorandom generators. Universal hashing provides strong guarantees for hashing-based algorithms and data structures.

• Universal hashing: a family H over universe U is c-universal if Pr[h(x)=h(y)] ≤ c/|B| for x≠y; pairwise independence with modular linear functions h_{a,b}(x) = (ax + b) mod p.
• Applications: expected O(1) hashing with chaining; perfect hashing (FKS); Cuckoo hashing (outline).
• Limited independence Chernoff: k-wise independence often suffices for concentration; tradeoffs vs seed length.
• Expander graphs and randomness amplification; expander walks for sampling and error reduction (high level).
• Pseudorandom generators (PRGs): fooling classes of tests; Nisan’s PRG for space-bounded computation (overview).
• Method of conditional expectations: converting randomized rounding/choices into deterministic ones.

1. Show that h_{a,b}(x) = ((ax + b) mod p) mod m with a≠0 over prime p defines a pairwise-independent family into m buckets.
2. Use the method of conditional expectations to derandomize selecting k items to maximize a linear objective under a knapsack constraint (outline).
3. Explain how limited-independence hash functions enable Chernoff-style bounds for load balancing with fewer random bits.