Symmetry Breaking
Ethernet.
Parallel Algorithms
PRAM
 $P$ processors, each with a RAM, local registers
 global memory of $M$ locations
 each processor can in one step do a RAM op or read/write to one global memory location
 synchronous parallel steps
 various conflict resolutions (CREW, EREW, CRCW)
 not realistic, but explores “degree of parallelism”
Randomization in parallel:
 load balancing
 symmetry breaking
 isolating solutions
Classes:
 NC: poly processor, polylog steps
 RNC: with randomization. polylog runtime, monte carlo
 ZNC: las vegas NC
 immune to choice of R/W conflict resolution
Practical observations:
 very little can be done in $o(\log n)$ with poly processors (binary tree of data aggregation usually needed)
 lots can be done in $\Theta(\log n)$
 often concerned about work which is processors times time
 algorithm is “optimal” if work equals best sequential
Basic operations
 and, or
 counting ones
 parallel prefix
Matching
 parallel algorithm for determinant
 based on parallel algorithm for matrix mult.
 Gives RNC algorithm for matching
Finding a Perfect Matching
We focus on bipartite; book does general case.
Last time, saw detection algorithm in $\RNC$:
 Tutte matrix
 Sumbolic determinant nonzero iff PM
 assign random values in $1,\ldots,2m$
 Matrix Mul, Determinant in $\NC$
How about finding one?
 If unique, no problem
 Since only one nozero term, ok to replace each entry by a 1.
 Remove each edge, see if still PM in parallel
 multiplies processors by $m$
 but still $\NC$
Idea:
 make unique minimum weight perfect matching
 find it
Isolating lemma: [MVV]
 Family of distinct sets over $x_1,\ldots,x_m$
 assign random weights in $1,\ldots,2m$
 Pr(unique minweight set)$\ge 1/2$
 Odd: no dependence on number of sets!
 (of course $< 2^m$)
Proof:
 Fix item $x_i$
 $Y$ is minvalue sets containing $x_i$
 $N$ is minvalue sets not containing $x_i$
 true minsets are either those in $Y$ or in $N$
 how decide? Value of $x_i$
 For $x_i=\infty$, minsets are $Y$
 For $x_i=+\infty$, minsets are $N$
 As increase from $\infty$ to $\infty$, single transition value when both $X$ and $Y$ are minweight
 If only $Y$ minweight, then $x_i$ in every minset
 If only $X$ minweight, then $x_i$ in no minset
 If both minweight, $x_i$ is ambiguous
 Suppose no $x_i$ ambiguous. Then minweight set unique!
 Exactly one value for $x_i$ makes it ambiguous given remainder
 So Pr(ambiguous)$=1/2m$
 So Pr(any ambiguous)$< m/2m=1/2$
Usage:
 Consider tutte matrix $A$
 Assign random value $2^{w_i}$ to $x_i$, with $w_i \in 1,\ldots,2m$
 Weight of matching is $2^{\sum w_i}$
 Let $W$ be minimum sum
 Unique w/pr $1/2$
 If so, determinant is odd multiple of $2^W$
 Try removing edges one at a time
 Edge in PM iff new determinant$/2^W$ is even.
 Big numbers? No problem: values have poly number of bits
$NC$ algorithm open.
For exact matching, $P$ algorithm open.
Parallel Maximal Independent set
trivial sequential algorithm
 inherently sequential
 from node point of view: each thinks can join MIS if others stay out
 randomization breaks this symmetry
Randomized idea
 each node joins with some probability
 all neighbors excluded
 many nodes join
 few phases needed
Algorithm:
 all degree 0 nodes join
 node $v$ joins with probability $1/2d(v)$
 if edge $(u,v)$ has both ends marked, unmark lower degree vertex
 put all marked nodes in IS
 delete all neighbors
Intuition: $d$regular graph
 vertex vanishes if it or neighbor gets chosen
 mark with probability $1/2d$
 prob (no neighbor marked) is $(11/2d)^d$, constant
 so const prob. of neighbor of $v$ markeddestroys $v$
 what about unmarking of $v$'s neighbor?
 prob(unmarking forced) only constant as argued above.
 So just changes constants
 const fraction of nodes vanish: $O(\log n)$ phases
 Implementing a phase trivial in $O(\log n)$.
For general case, define good vertices
 vertex disappears if neighbor in IS
 for which vertices is this likely?
 good: at least $1/3$ neighbors have lower degree
 prob. no neighbor of good marked $\le (11/2d(v))^{d(v)/3} \le e^{1/6}$.
 So some neighbor marked with prob. $1e^{1/6}$
Prob any node chosen for IS, given marked, exceeds $1/2$
 suppose $w$ marked.
 only unmarked if higher degree neighbor marked
 higher degree neighbor marked with prob. $\le 1/2d(w)$
 only $d(w)$ such neighbors
 prob. any superior neighbor marked at most $1/2$ (union bound).
Combine
 conclude prob. good node gets neighbor in IS at least $\frac12(1e^{1/6})$
 If so, good node is deleted
 i.e., good node deleted with constant probability.
 Problem: perhaps only one good vertex?
Good edges
 any edge with a good neighbor
 has prob. $\alpha$ to vanish
 show half edges good
 if $m_j$ is number of edges after $j$ iters, have shown \[ E[m_j \mid m_{j1}] \le (1\alpha/2)m_{j_1} \]
 So, constant probability of reducing by constant factor
 So, $O(\log m)$ iters suffice to reduce by polynomial (Chernoff)
Proof
 Let $V_B$ be bad vertices; we count edges with both ends in $V_B$.
 direct edges from lower to higher degree $d_i$ is indegree, $d_o$ outdegree
 if $v$ bad, then $d_i(v) \le d(v)/3$
 deduce \[\sum_{V_B} d_i(v) \le \frac13 \sum_{V_B} d(v)=\frac13\sum_{V_B}( d_i(v)+d_o(v)) \]
 so $\sum_{V_B} d_i(v) \le \frac12 \sum_{V_B} d_o(v)$
 which means indegree can only “catch” half of outdegree; other half must go to good vertices.
 assign each bad edge incoming $v$ to distinct two edges leaving $v$.
 proves all edges at least twice bad edges
 ie as many good as bad

more carefully,
 $d_o(v)d_i(v) \ge \frac13(d(v))=\frac13(d_o(v)+d_i(v))$.
 Let $V_G,V_B$ be good, bad vertices
 degree of bad vertices is $$ \begin{eqnarray*} 2e(V_B,V_B)+e(V_B,V_G)+e(V_G,V_B) &= & \sum_{v\in V_B} d_o(v)+d_i(v)\\ &\le &3\sum(d_o(v)d_i(v))\\ &= &3(e(V_B,V_G)e(V_G,V_B))\\ &\le &3(e(V_B,V_G)+e(V_G,V_B) \end{eqnarray*} $$ Deduce $e(V_B,V_B) \le e(V_B,V_G)+e(V_G,V_B)$. result follows.
Derandomization:
 Analysis focuses on edges,
 so unsurprisingly, pairwise independence sufficient
 We used two lemmas.
 First that marked vertex probably stays marked
 But this only used union bound
 So still OK with pairwise independence
 Where did we use independence? to lower bound prob. pick
neighbor of good vertex.
 let $X_i$ be event to pick $i^{th}$ neighbor
 Write $p_i=\Pr[X_i]$
 he know for good vertex, $\sum p_i \ge \frac{d(v)}{3}\cdot\frac{1}{2v}$
 If $X_i$ independent that $\Pr[\cup X_i] \ge 1\prod (1p_i)$
 Analogue for pairwise: $\Pr[\cup X_i] \ge \frac12\min (\frac12,\sum p_i)$
 “Markovlike”
 Markov upper bounds using sum
 Lower bound by taking second inclusionexclusion term
 (Might hope to use Chebyshev here, but that fails when $\sum p_i \le 1$.)
 Proof.
 Suppose $\sum p_i \le 1$ $$ \begin{align*} \Pr[\cup X_i]&\ge \sum \Pr[X_i]  \sum_{i < j} \Pr[X_i \cap X_j]\\ &= \sum p_i  \sum_{i < j} p_ip_j\\ &= \sum p_i  \frac12 \sum_{i \ne j} p_ip_j\\ &\ge \sum p_i \frac12 \sum p_ip_j\\ &= \sum p_i \frac12 (\sum p_i)^2\\ &= \sum p_i(1\frac12 \sum p_i)\\ &\ge \frac12 \sum p_i \end{align*} $$
 Else if some $p_i > 1/2$, done ($X_i$ probably 1).
 Else $\sum p_i >1$, so discard $X_i$'s (each of $p_i< 1/2$ until $\frac12 < \sum p_i < 1$.
 First case applies to this subset.
 Combine lemmas. $$ \begin{align*} \Pr[v\mbox{ deleted}] &= \Pr[N(v)\mbox{marked and stays}]\\ &=\Pr[N(v)\mbox{ stays} \mid N(v)\mbox{ marked}]\Pr[N(v) \mbox{ marked}]\\ &\ge \alpha \Pr[N(v)\mbox{ stays} \mid N(v)\mbox{ marked}] \end{align*} $$
with care, $O(m)$ processors and $O(\log n)$ time (randomized)
LFMIS Pcomplete.