Randomized Algorithms (Spring 2010)/Fingerprinting: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
| Line 1: | Line 1: | ||
== Fingerprinting == | == Fingerprinting == | ||
=== | === Evaluating random point === | ||
=== Checking | ==== 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) == | == Probabilistic Checkable Proofs (PCPs) == | ||