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 min-weight set)$\ge 1/2$
• Odd: no dependence on number of sets!
• (of course $< 2^m$)

Proof:

• Fix item $x_i$
• $Y$ is min-value sets containing $x_i$
• $N$ is min-value sets not containing $x_i$
• true min-sets are either those in $Y$ or in $N$
• how decide? Value of $x_i$
• For $x_i=-\infty$, min-sets are $Y$
• For $x_i=+\infty$, min-sets are $N$
• As increase from $-\infty$ to $\infty$, single transition value when both $X$ and $Y$ are min-weight
• If only $Y$ min-weight, then $x_i$ in every min-set
• If only $X$ min-weight, then $x_i$ in no min-set
• If both min-weight, $x_i$ is ambiguous
• Suppose no $x_i$ ambiguous. Then min-weight 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 $(1-1/2d)^d$, constant
• so const prob. of neighbor of $v$ marked---destroys $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 (1-1/2d(v))^{d(v)/3} \le e^{-1/6}$.
• So some neighbor marked with prob. $1-e^{-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(1-e^{-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_{j-1}] \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 (1-p_i)$
  • Analogue for pairwise: $\Pr[\cup X_i] \ge \frac12\min (\frac12,\sum p_i)$
  • “Markov-like”
    • Markov upper bounds using sum
    • Lower bound by taking second inclusion-exclusion 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 P-complete.