Symmetry Breaking
Ethernet.
- each node transmit prob. $1/n$
- gives constant chance of one getting through.
- now generalize.
- Application: wireless broadcast networks
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
- what about recursive?
- 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
- what about exact?
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$
- square $G$ to get adjacency $A'$, compute distance $D'$
- 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
- Add
- $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'$
- parities suffice:
- Result: all distances in $O(M(n)\log n)$ time.
To find paths: Witness product
- example: tripartite one-hop hop case
Modify matrix alg:
- easy case: unique witness
- multiply column $c$ by $c$.
- read off witness identity
- 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