Randomized Algorithms (Spring 2010)/Fingerprinting: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
| Line 4: | Line 4: | ||
==== Example: Checking matrix multiplication ==== | ==== Example: Checking matrix multiplication ==== | ||
Consider the following problem: | |||
* 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>. | ||
* | |||
==== Example: Checking polynomial identities ==== | ==== Example: Checking polynomial identities ==== | ||
Revision as of 12:47, 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].
Example: Checking polynomial identities
Evaluating over a random field
Example: Identity checking
Example: Randomized pattern matching
Universal hashing
- Example: checking distinctness