Randomized Algorithms (Spring 2010)/Fingerprinting

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

Fingerprinting

Evaluating at random points

Example: Checking matrix multiplication

Consider the following problem:

  • Given as the input three [math]\displaystyle{ n\times n }[/math] matrices [math]\displaystyle{ A,B }[/math] and [math]\displaystyle{ C }[/math],
  • check whether [math]\displaystyle{ C=AB }[/math].
Algorithm (Freivalds)
  • Pick a vector [math]\displaystyle{ r \in\{0, 1\}^n }[/math] uniformly at random.
  • If [math]\displaystyle{ A(Br) = Cr }[/math] then return "yes" else return "no".

If [math]\displaystyle{ AB=C }[/math] then [math]\displaystyle{ A(Br) = Cr }[/math] for any [math]\displaystyle{ r \in\{0, 1\}^n }[/math], thus the algorithm always returns "yes".

Lemma
If [math]\displaystyle{ AB\neq C }[/math] then for a uniformly random [math]\displaystyle{ r \in\{0, 1\}^n }[/math],
[math]\displaystyle{ \Pr[A(Br) = Cr]\le \frac{1}{2} }[/math].

Example: Checking polynomial identities

Algorithm (Schwartz-Zippel)
  • pick [math]\displaystyle{ r_1, \ldots , r_n }[/math] independently and uniformly at random from a set [math]\displaystyle{ S }[/math];
  • if [math]\displaystyle{ P_1(r_1, \ldots , r_n) = P_2(r_1, \ldots , r_n) }[/math] then return “yes” else return “no”;

Evaluating over a random field

Example: Identity checking

Example: Randomized pattern matching

Universal hashing

Example: checking distinctness

Probabilistic Checkable Proofs (PCPs)