\documentclass[12pt]{article} \usepackage{wide,me} \parindent0pt


Basic idea: compare two things from a big universe $U$

We work with fields

Verifying matrix multiplications:

Freivald's technique:

In general, many ways to fingerprint explicitly represented objects. But for implicit objects, different methods have different strengths and weaknesses.

We'll fingerprint 3 ways:

All are functions mapping large input space to small output space.

String matching


Trouble if $a=b \pmod p$. How avoid? How likely?

Do we need a prime?

How find prime?

Pattern matching in strings

Rabin-Karp algorithm

Bloom Filters

Hash tables are good for key to value mappings,



Formally validate our assumption that have $pm$ zeros.