Randomized Algorithms (Spring 2010)/Fingerprinting

From TCS Wiki
Revision as of 12:36, 2 June 2010 by imported>WikiSysop (→‎Fingerprinting)
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)

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=Randomized_Algorithms_(Spring_2010)/Fingerprinting&oldid=2771"