Randomized Algorithms (Spring 2010)/Fingerprinting: Difference between revisions

From TCS Wiki
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

Probabilistic Checkable Proofs (PCPs)