Randomized Algorithms (Spring 2010)/Fingerprinting: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
| Line 15: | Line 15: | ||
=== Universal hashing === | === Universal hashing === | ||
;Example: checking distinctness | ;Example<nowiki>:</nowiki> checking distinctness | ||
== Probabilistic Checkable Proofs (PCPs) == | == Probabilistic Checkable Proofs (PCPs) == | ||
Revision as of 12:37, 2 June 2010
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