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

Fingerprints by Polynomials

Good for fingerprinting “composable” data objects.

Small problem:

String checksum:

Multivariate:

Proof:

Perfect matching

Wait, det may be huge!

Finding the Matching

We now have a way to decide if a matching exists.

Self reducibility

For perfect matching

Network Coding

A communication task:

Coding solution

Multiple receivers

This is the key idea of network coding. It generalizes to arbitrary communication graphs.