Randomized Algorithms (Spring 2010)/Fingerprinting

From TCS Wiki
Revision as of 12:37, 2 June 2010 by imported>WikiSysop (→‎Universal hashing)
Jump to navigation Jump to search

Fingerprinting

Evaluating random point

Example: Checking matrix multiplication

Example: Checking polynomial identities

Evaluating over a random field

Example: Identity checking

Randomized pattern matching

Universal hashing

Example: checking distinctness

Probabilistic Checkable Proofs (PCPs)