Randomized Algorithms (Spring 2010)/Fingerprinting
Fingerprinting
Evaluating at random points
Example: Checking matrix multiplication
Example: Checking polynomial identities
Evaluating over a random field
Example: Identity checking
Randomized pattern matching
Universal hashing
- Example: checking distinctness