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

Fingerprinting

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

Checksums:

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,

Algorithm

Analysis

Formally validate our assumption that have $pm$ zeros.