Randomized Algorithms (Spring 2010)/Fingerprinting: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
| Line 7: | Line 7: | ||
* Given as the input three <math>n\times n</math> matrices <math>A,B</math> and <math>C</math>, | * Given as the input three <math>n\times n</math> matrices <math>A,B</math> and <math>C</math>, | ||
* check whether <math>C=AB</math>. | * check whether <math>C=AB</math>. | ||
{|border="1" | |||
|'''Algorithm (Freivalds)''' | |||
:*Pick a vector <math>r \in\{0, 1\}^n</math> uniformly at random. | |||
:*If <math>A(Br) = Cr</math> then return "yes" else return "no". | |||
|} | |||
If <math>AB=C</math> then <math>A(Br) = Cr</math> for any <math>r \in\{0, 1\}^n</math>, thus the algorithm always returns "yes". | |||
{|border="1" | |||
|'''Lemma''' | |||
:If <math><math>AB\neq C</math></math> then for a uniformly random <math>r \in\{0, 1\}^n</math>, | |||
::<math>\Pr[A(Br) = Cr]\le \frac{1}{2}</math>. | |||
|} | |||
==== Example: Checking polynomial identities ==== | ==== Example: Checking polynomial identities ==== | ||
Revision as of 12:54, 2 June 2010
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)
|
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
|
Example: Checking polynomial identities
Evaluating over a random field
Example: Identity checking
Example: Randomized pattern matching
Universal hashing
- Example: checking distinctness