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

## Symmetry Breaking

Ethernet.

• each node transmit prob. $1/n$
• gives constant chance of one getting through.
• now generalize.

### Shortest Paths

classical shortest paths.

• dijkstra's algorithm
• floyd's algorithm. similarity to matrix multiplication

Matrices

• length 2 paths by squaring
• matrix multiplication. strassen.
• shortest paths by “funny multiplication.”
• huge integer implementation
• base-$(n+1)$ integers

Boolean matrix multiplication

• easy.
• gives objects at distance 2.
• gives $nMM(n)$ algorithm for problem
• well can get to within 2: let $T_k$ be boolean “distance less than or equal to $2^k$.” Squaring gives $T_{k+1}$.
• $O(\log n)$ squares for unit length

Seidel's distance algorithm for undirected, unit lengths.

• log-size integers:
• parities suffice:
• square $G$ to get adjacency $A'$, compute distance $D'$
• if $D_{ij}$ even then $D_{ij} = 2D'_{ij}$
• if $D_{ij}$ odd then $D_{ij} = 2D'_{ij}-1$
• need a (fast, batch) way to distinguish these two cases for $D_{ij}$.
• For neighbors $i,k$,
• $D_{ij}-1 \le D_{kj} \le D_{ij}+1$
• exists $k$, $D_{kj} = D_{ij}-1$
• Parities
• Note $D'$ are $D/2$ rounded up
• So if $D_{ij}$ even, then $D'_{kj} \ge D'_{ij}$ for every neighbor $k$
• And if $D_{ij}$ odd, then $D'_{kj} \le D'_{ij}$ for every neighbor $k$, and strict for at least one
• $D_{ij}$ even iff $S_{ij}=\sum_{k} D'_{kj} \ge D_{ij} d(i)$
• $D_{ij}$ odd iff $\sum_{k} D'_{kj} < D_{ij} d(i)$
• How determine? find $S=AD'$
• Result: all distances in $O(M(n)\log n)$ time.
This is deterministic distance algorithm.

To find paths: Witness product

• example: tripartite one-hop hop case

Modify matrix alg:

• easy case: unique witness
• multiply column $c$ by $c$.
• reduction to easy case:
• Suppose $r$ columns have witness
• Suppose choose each with prob. $p$
• Prob. exactly 1 witness: $rp(1-p)^{r-1} \approx 1/e$
• Try all values of $r$
• Wait, too many.
• Approx
• Suppose $p = 2/r$
• Then prob. exactly 1 is $\approx 2/e^2$
• So anything in range $1/r \ldots 1/2r$ will do.
• So try $p$ all powers of 2.
• suppose $2^c \le r \le 2^{c+1}$
• choose each column with probability $2^{-c}$.
• prob. exactly one witness: $r\cdot 2^{-c} (1-2^{-c})^{r-1} \ge (1/2)(1/e^2)$
• so try $\log n$ distinct powers of 2, each $O(\log n)$ times
• Use to find shortest paths in general
• Find distances
• for each node, dest, find neighbor with distance one less
• boolean matrix $R$ of “distance is $d-1$”
• boolean witness product of $RA$
• since then $(RA)_{ij}$ is $\sum_{k \in N(j)} R_{ik}$
• i.e. 1 if some neighbor of $j$ has distance $d-1$ to $i$
• this is right “step” from $i$ to $j$
• witness product finds one
• $n$ matrix muls---too slow.
• Mod 3:
• Recall some neighbor distance down by one
• so compute distances mod 3.
• suppose $D_{ij} = 1 \bmod 3$
• then look for $k$ neighbor of $i$ such that $D_{kj}= 0 \bmod 3$
• let $D_{ij}^{(s)}=1$ iff $D_{ij} = s \bmod 3$
• than $AD^{(s)}$ has $ij=1$ iff a neighbor $k$ of $i$ has $D_{kj}^{(s)}$
• so, witness matrix mul!
• Witness product can be derandomized
• only via small sample space
• based on “small bias” distribution of bits: all subset parities are within $\epsilon$ of 50-50 distribution
• sample space size is only polylogarithmic
• so yields fast deterministic algorithm
• or efficient randomized one
• no “normal” deterministic algorithm