Selecting k-th element
Approximate Matrix Multiplication
Frequency moments in Streaming Data
A Maximum Minor sum problem
Approximating max-cut in weighted graphs
Packet Routing in Hypercube Networks
Uniform generation and rapid convergence
Backward analysis for randomized sorting/searching
Polynomial testing, fingerprinting and applications
Randomization in geometric algorithms (see course page talk)
Global Min-cut
Dynamic Connectivity
Online cache management