Randomized Algorithms (Spring 2010)/Fingerprinting: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
| Line 5: | Line 5: | ||
==== Example: Checking matrix multiplication ==== | ==== Example: Checking matrix multiplication ==== | ||
{|border="1" | {|border="1" | ||
: | | | ||
*'''Input''': Three <math>n\times n</math> matrices <math>A,B</math> and <math>C</math>. | |||
*'''Question''': Is <math>C=AB</math>? | |||
|} | |} | ||
Revision as of 12:42, 2 June 2010
Fingerprinting
Evaluating at random points
Example: Checking matrix multiplication
|
Example: Checking polynomial identities
Evaluating over a random field
Example: Identity checking
Example: Randomized pattern matching
Universal hashing
- Example: checking distinctness