Randomized Algorithms (Spring 2010)/Fingerprinting

From TCS Wiki
Revision as of 12:42, 2 June 2010 by imported>WikiSysop (→‎Example: Checking matrix multiplication)
Jump to navigation Jump to search

Fingerprinting

Evaluating at random points

Example: Checking matrix multiplication

  • Input: Three [math]\displaystyle{ n\times n }[/math] matrices [math]\displaystyle{ A,B }[/math] and [math]\displaystyle{ C }[/math].
  • Question: Is [math]\displaystyle{ C=AB }[/math]?

Example: Checking polynomial identities

Evaluating over a random field

Example: Identity checking

Example: 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=2777"