Fingerprints by Polynomials

Good for fingerprinting “composable” data objects.

• check if $P(x)Q(x)=R(x)$
• $P$ and $Q$ of degree $n$ (means $R$ of degree at most $2n$)
• mult in $O(n\log n)$ using FFT
• evaluation at fixed point in $O(n)$ time
• Random test:
  • $S \subseteq F$
  • pick random $r \in S$
  • evaluate $P(r)Q(r)-R(r)$
  • suppose this poly not 0
  • then degree $2n$, so at most $2n$ roots
  • thus, prob (discover root) $\le 2n/|S|$
  • so, eg, sufficient to pick random int in $[0,4n]$
  • Note: no prime needed (but needed for $Z_p$ sometimes)
• Again, major benefit if polynomial implicitly specified.

Small problem:

• degree $n$ poly can generate huge values from small inputs.
• Solution 1:
  • If poly is over $Z_p$, can do all math mod $p$
  • Need $p$ exceeding coefficients, degree
  • doesn't change number of roots
  • $p$ need not be random---pick once in advance
• Solution 2:
  • Work in $Z$, deduce nonzero evaluation because few roots
  • e.g. evaluate at random $0 \le x \le n^2$ for high probability
  • deduce nonzero mod random $q$ (as in string matching)
  • so do all computation mod $q$
  • $q$ value must exceed bits (i.e. log) of evaluated value
  • if max coefficient is $a$ then value is at most $an(n^2)^n$
  • so $q$ can be $O(\log a + n \log n)$.
• Again, major benefit if polynomial implicitly specified.

String checksum:

• treat as degree $n$ polynomial
• eval a random $O(\log n)$ bit input,
• prob. get 0 small

Multivariate:

• $n$ variables
• degree of term: sum of vars' degrees
• total degree $d$: max degree of term.
• Schwartz-Zippel: fix $S \subseteq F$ and let each $r_i$ random in $S$ \[ \Pr[Q(r_i)=0 \mid Q \ne 0] \le d/|S| \] Note: no dependence on number of vars!

Proof:

• induction. Base done.
• $Q \ne 0$. So pick some (say) $x_1$ that affects $Q$
• write $Q=\sum_{i \le k} x_1^iQ_i(x_2,\ldots,x_n)$ with $Q_k() \ne 0$ by choice of $k$
• $Q_k$ has total degree at most $d-k$
• By induction, prob $Q_k$ evals to 0 is at most $(d-k)/|S|$
• suppose it didn't. Then $q(x)=\sum x_1^i Q(r_2,\ldots,r_n)$ is a nonzero univariate poly.
• by base, prob. eval to 0 is $k/|S|$
• add: get $d/|S|$
• why can we add? $$ \begin{eqnarray*} \Pr[E_1] &= &\Pr[E_1 \cap \overline{E_2}]+\Pr[E_1 \cap E_2]\\ &\le & \Pr[E_1 \mid \overline{E_2}] + \Pr[E_2] \end{eqnarray*} $$

Perfect matching

• Define
• by max-flow techniques, get $m\sqrt{n} \le n^{2.5}$
• Edmonds matrix: variable $x_{ij}$ if edge $(u_i,v_j)$
• determinant nonzero if PM
• poly nonzero symbolically.
  • so apply Schwartz-Zippel
  • Degree is $n$
  • So number $r\in(1,\ldots,n^2)$ yields 0 with prob. $1/n$
• Determinant can be computed with $n^{2.376...}$ ops.

Wait, det may be huge!

• Shwartz-Zippel applies in any field
• So pick work mod $p$, with $p>n^2$ to keep failure prob. small
• Note all coefficients of determinant polynomial are 1
• So determinant polynomial is still (symbolically) nonzero mod $p$

Finding the Matching

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

• But can we find it?

Self reducibility

• General technique for solving construction/optimization via decision
• Use repeated calls to decision to “steer towards” output solution

For perfect matching

• Remove an edge
• Check if still have perfect matching.
• If not, put it back
• When done, all that's left is perfect matching.
• time is $m$ determinants
• not great time, but really simple algorithm!

Network Coding

Motivation

• In traditional network protocols a node receives a message and forwards it to a “next hop”
• can model this with a graph where each edge can carry on message per time step
• disjoint paths can carry distinct messages at the same time
• achievable $s$-$t$ throuput is just number of disjoint $s$-$t$ paths, i.e. $s$-$t$ max-flow
• which we know equals $s$-$t$ min-cut
• different length paths might have different latency
• but can start a new message each time step, so doesn't affect throughput

Problems

• have to compute max-flow
• graph might change, forcing recomputation

Multicast

• what if multiple recipients want same messages?
• e.g. streaming video (netflix)
• do we need to use twice as many paths to send to two recipients?
• seems wasteful. could perhaps send message out on a “multicast tree” which uses same path for most of the way?
• the dream: maybe if each recipient has enough throughput separately, can transmit to all of tham at the same time?
• for broadcast (every node a recipient), Edmonds proved this is possible (disjoint trees)
• for multicast (only some nodes want it), counterexample: the butterfly

Network coding

• Ahlswede et al.
  • realized routers are not dumb---they can compute over the incoming packets!
  • each outgoing edge can carry some function of incoming packets
  • solves butterfly problem
  • solves multicast: can do multicast using network coding if and only if each sink has enough capacity to receive separately
  • no polytime construction
• Koetter and Medard showed that for multicast linear network coding suffices
  • each outgoing edge sends some linear combination of incoming messages
  • by induction, each sink receives some linear combination of original messages
  • if determinant of matrix is nonzero, can invert to recover!
  • proved that if each sink is separately feasible, can construct multicast solution with linear network codes
  • polynomial time, but complicated! Hilbert's Nullstelensatz, Groebner bases

Special case to consider:

• $2n$-vertex bipartite graph with source and sink vertices
• source has $n$ messages to send to $t$
• each edge can carry one message in one time step
• one solution: send along perfect matching
• requires computing perfect matching

Coding solution

• think of messages as integers mod $p$
• $s$ sends one message to each LHS
• each LHS sends its message to all RHS neighbors
• each RHS neighber sends $t$ a random linear combination of what it got, mod $p$
• can $t$ “decode” the message?
• yes (assuming it knows the random coefficients).
• What is the linear operator (called “transfer matrix”) mapping $n$ inputs (from $s$) to $n$ outputs (at $t$)?
• it's the Edmonds matrix of the bipartite graph, with random coefficients in it
• we proved this has nonzero determinant whp
• which means it is invertible
• so $t$ can invert the linear function to reconstruct input.

How can source know transfer matrix?

• for first $n$ rounds, have $s$ send $n$ distinct unit vectors
• lets $t$ read off columns of transfer matrix
• then use it for all future rounds
• more sophisticated schemes can adapt over time
• e.g., imagine that each “super-round” message contains many $>>n$ rounds of numbers
• then you can make the first $n$ rounds of each message encode the $n$ unit vectors without wasting a lot of space

Multiple receivers

• same bipartite core
• $s$ has $k< n$ messages
• multiple $t_i$ each connected to some $k$ RHS vertices
• can send to any one $t_i$ over the perfect matching to that $t_i$
• but coding argument above says RLC also sends to $t_i$ ($k\times k$ transfer matrix)
• but this is true for all receivers simultaneously
• since each can receive, all can receive.

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

Delay

• we focused on one “round” of messages for simplicity
• if nodes want to transmit new messages in each time step, and paths have different lengths, then messages at different times can get combined with each other
• this can be handled
• intuitively, you learn about early rounds and subtract them from later rounds