\documentclass{article}
\input{6856-preamble}

\begin{document}
\psetnum{6}
\date{2005/03/16}
\collab{Collaborators: $\set{\mathtt{sarahl}, \mathtt{gpickard}}$}

\begin{pset}
  \begin{problem}
    \begin{subproblem}
      We claim that the set of vertices output over all phases is a
      maximal independent set. It is an independent set because during
      each phase, one vertex corresponding to every edge is deleted,
      so no adjacent vertices are added during one phase, and the
      neighbors of every vertex are deleted, so no adjacent vertices
      are added during the next phase. We can see that it is maximal
      because a vertex is deleted only when it is added to the set
      or when one of its neighbors is added. Since there are no
      vertices remaining at the end, one of these is true in every
      vertex. So the set is maximal because no more vertices can be
      added.
    \end{subproblem}

    \begin{subproblem}
      Suppose a vertex $v$ has degree $d$. The vertex remains marked
      as long as it is the lower-weight endpoint of each of its edges,
      i.e. if it has lower weight than any of its $d$ neighbors. Since
      the weights of the vertices are determined uniformly at random,
      we can consider their relative rankings to be uniformly
      distributed. Thus, in the set consisting of $v$ and its $d$
      neighbors, $v$ has the lowest weight with probability
      $\frac{1}{d+1}$.

      This analysis assumes that no two vertices are assigned the same
      weight. We will ensure that unique weights are assigned to the
      vertices by checking whether any two vertices have the same
      weight, and if so generating new random weights, and repeating
      if necessary. This can be performed in parallel using one
      processor per pair of vertices. The probability that two
      vertices are assigned the same weight from a set of $n^4$
      weights is $\frac{n}{n^4} = \frac{1}{n^3}$, which is small
      enough that with high probability $\log n$ attempts
      will succeed.
    \end{subproblem}

    \begin{subproblem}
      We use the same definition of a good vertex: a vertex $v$ is
      good if it has at least $\frac{d(v)}{3}$ neighbors of degree no
      more than $d(v)$. We claim that a good vertex is removed from
      the graph in a given phase with constant probability. A vertex
      is removed from the graph if it or one of its neighbors remains
      marked. We consider the probability of some neighbor of a good
      vertex $v$ being selected for the IS. Each neighbor $u$ will be
      added to the IS with probability $\frac{1}{d(u) + 1}$ from
      above. Since $v$ is good, it has at least $\frac{d(v)}{3}$
      neighbors of degree no more than $d(v)$. Each of these neighbors
      will be selected for the IS with probability at least
      $\frac{1}{d(v) + 1}$, so the probability that $v$ is removed in
      a given phase is at least
      \[ \frac{\frac{d(v)}{3}}{d(v) + 1} = \frac{1}{3 +
        \frac{3}{d(v)}} \ge \frac{1}{6} \]
      since $d(v)$ is at least 1.

      Now we have proven that a good vertex is removed from the graph
      in a given phase with constant probability. In class we showed
      that if any edge with a good neighbor has constant probability
      $\alpha$ to be removed --- which �is precisely what we have just
      proven --- $\bigO{\log m}$ iterations suffice to
      reduce the number of edges by a polynomial factor, and so we
      have a $\RNC$ algorithm.
    \end{subproblem}
  \end{problem}

  \begin{problem}
    We want to determine the successor matrix representation of the
    all-pairs shortest path in a graph where edge lengths are integers
    from $1$ to $B$. Recall that we can perform a witnessed Boolean
    matrix multiplication in $\bigO{MM(n) \log^2 n}$ time. We modify
    Seidel's algorithm slightly to handle the non-unit edge lengths.

    The distance between two neighboring vertices $i$ and $k$ and some
    other vertex $k$ no longer differs by 1 but rather by $B$, so we
    have the inequalities
    \begin{align}
      \label{eq:pmb}
      \forall k &\;\; D_{ij} - B \le D_{kj} \le D_{ij} + B \\
      \label{eq:existsk}
      \exists k &\;\; D_{kj} = D_{ki} + D_{ij}
    \end{align}

    Rather than consider distances mod 3 as in Seidel's algorithm, we
    consider distances mod $2B + 1$.
%     For neighbors $i$ and $k$, if
%     $D_{ij} \equiv D_{ki} + D_{ij} \pmod{2B+1}$ then $D_{ij} = D_{ki}
%     + D_{ij}$ by Equation~\ref{eq:pmb}.
    If $k$ is a neighbor on the shortest path from $i$ to $j$, then
    $D_{kj} = D_{ki} + D_{ij}$; by Equation~\ref{eq:pmb} this is true
    if and only if $D_{kj} \equiv D_{ki} + D_{ij}$, and by
    Equation~\ref{eq:existsk} a neighbor $k$ satisfying this condition
    must exist. We define the Boolean matrix $D^{(s)}$ to have
    $D^{(s)}_{kj} = 1$ iff $D_{kj} \equiv s \pmod{2B+1}$. Then $k$ is
    on the shortest path from $i$ to $j$ if $D_{ij} = D_{ik} +
    D_{kj}$, which is the case when there exists some integer $x$ ($1
    \le x \le 2B+1$) such that $D^{(x)}_{ik} = 1$ and $D^{(D_{kj} - x
      \bmod 2B+1)}_{kj} = 1$. This is exactly when $\left(D^{(x)}
      D^{(D_{kj} - x \bmod 2B+1)}\right)_{ij} = 1$. Furthermore, we
    can use a witnessed Boolean matrix multiplication of these two
    matrices to identify the successor $k$.

    Define $W^{(x,d)}$ to be the witnessed product $\left(D^{(x)} D^{d
        - x \bmod 2B+1)}\right)$. Since computations are performed
    modulo $2B+1$, there are only $\bigO{B}$ possible values for and
    $x$ and $d$, and so we can compute all the $W^{(x,d)}$ matrices
    with $\bigO{B^2}$ witnessed multiplications. Then it is
    straightforward to compute our successor matrix from these:
    \[S_{ij} = W^{(x, D_{ij})} \text {  for any } x \text { such that
    } W^{(x, D_{ij})}\text{ is non-zero.}\]

    This algorithm requires $\bigO{B^2 MM(n) \log^2 n}$ time.
  \end{problem}

  \begin{problem}
    We consider the problem of finding a minimum-weight perfect
    matching in a bipartite graph $G$. Our algorithm is essentially the
    same as in the unweighted case, except that the edges now have
    initial weight. As before, we generate a graph $G'$ that is likely to
    have a unique perfect matching. We do so by scaling up the initial
    edge weights by a factor of $4mn$, then adding a perturbation
    selected uniformly at random from $1$ to $2m$. The remainder of
    the algorithm is exactly as in the unweighted case.

    To show correctness, we first show that a minimum-weight matching
    $\alpha$ in $G'$ will indeed always be a minimum weight matching
    in the original graph $G$. The matching is minimum weight in $G'$,
    so no other matching has lower weight in $G'$. The only case in
    which this would not be a minimum-weight matching in $G$ would be
    if there were some other matching $\beta$ that had lower weight in
    $G$ but higher weight in $G'$. We show that this is impossible.
    Let $w_{\alpha}'$ be $\alpha$'s weight in $G'$, and $w_{\alpha}$
    be $\alpha$'s weight in $G$. By definition, $w_{\alpha}' =
    (4mn)w_\alpha + x$ for some perturbation $x$. Similarly, $w_\beta'
    = (4mn)w_\beta + y$ for some other perturbation $y$, which is at
    least $(4mn)(w_\alpha + 1) + y$, since edge weights are integers.
    So
    \[ w_\beta' - w_\alpha' \ge (4mn)(w_\alpha + 1) + y -
    \left((4mn)w_\alpha + x\right) = 4mn + y - x \] But $y$ and $x$
    are the total perturbations on a matching; since each matching has
    $n$ edges and each edge receives perturbation at most $2m$, $x$
    and $y$ are both bounded by $2mn$. So $w_\beta' - w_\alpha'$ will
    never be negative and so $\beta$ with lower weight in $G$ but
    higher weight in $G'$ can exist.

    Now we need only show that it is likely that $G'$ will have a
    unique minimum-weight perfect matching. The proof is based on the
    Isolating Lemma. First, note that the result above proves there is
    no danger of a perfect matching with minimum weight in $G$
    becoming a minimum-weight matching in $G'$. So we can safely
    ignore all perfect matchings that do not have minimum weight in
    $G$. Let $\mathscr{F}$ be the set of perfect matchings with
    minimum weight in $G'$. Each of these matchings has the same
    weight; call it $w$. So we can subtract away each edge's initial
    weight, reducing the set system to the unweighted case. This gives
    a set system $(X, \mathscr{F})$ where $X$ is the set of (now
    unweighted) edges, and each edge receives a random weight chosen
    uniformly and independently from $1$ to $2m$. The isolating lemma
    tells us that there is a unique minimum weight set in
    $\mathscr{F}$ with probability at least $\nicefrac12$. This means
    that with probability $\nicefrac12$, there is a perfect matching
    in $\mathscr{F}$ that has a unique minimum perturbation added to
    it. Since every perfect matching in $\mathscr{F}$ had minimum
    weight in $G'$, a matching in $\mathscr{F}$ with unique minimum
    perturbation is a unique minimum-weight perfect matching, and so
    our algorithm for finding unique minimum-weight perfect matchings
    can find it. This proves the claim.

    Note that this algorithm is clearly in $\RNC$ because the scaling
    and random perturbation of edge weights can be performed in
    parallel, then the $\RNC$ algorithm for finding the matching can
    be applied.
  \end{problem}

  \begin{problem}
    \begin{subproblem}
      Define $Y$ to be the random variable giving the number of hits
      that occur with $n$ samples, i.e. $X = \sum_{i=1}^n
      I_i$. Certainly $\Exp{X} = np$ and so our estimator is $\hat{p}
      = \frac1n Y$. We wish to obtain a $\hat{p}$ such that
      $\Pr{\abs{\hat{p}-p} > \epsilon} \le \delta$. Equivalently,
      $\Pr{\abs{Y-np} > n\epsilon} \le \delta$.

      Recall the additive form of the Chernoff bound:
      \begin{lemma}[Chernoff]
        If $X$ is a sum of $n$ independent random variables with mean
        $\mu$, then
        \begin{align*}
          \Pr{X-\mu > n\epsilon} &\le e^{-2n\epsilon^2} \\
          \Pr{X-\mu < -n\epsilon} &\le e^{-2n\epsilon^2}
        \end{align*}
      \end{lemma}
      
      This gives the immediate corollary that
      \[ \Pr{\abs{X-\mu} > n\epsilon} \le 2e^{-2n\epsilon^2} \]

      We can apply this bound to $Y$, since it is a sum of independent
      indicator
      random variables. Since $\mu_Y = np$, we obtain
      \[ \Pr{\abs{Y-np} > n\epsilon} \le 2e^{-2n\epsilon^2} \]
      We want this to occur with probability at most $\delta$, so
      \begin{align*}
        2e^{-2n\epsilon^2} &\le \delta \\
        -2n\epsilon^2 &\le \ln \nicefrac\delta2 \\
        2n\epsilon^2 &\ge \ln \nicefrac2\delta \\
        n &\ge \frac{1}{2\epsilon^2} \ln \nicefrac2\delta
      \end{align*}
    \end{subproblem}

    \begin{subproblem}
      Suppose we have an estimation algorithm that estimates $p$ to
      within a multiplicative factor of $(1 \pm \epsilon)$ with error
      probability $\nicefrac14$ and wish to reduce this error
      probability to some $\delta$ by performing $k$ estimations and
      taking the median. We give a bound on $k$ as a function of
      $\delta$.

      Let $X$ be the median of $k$ estimations. We first consider
      $\Pr{X > (1+\epsilon) p}$. Note that this only occurs if at
      least $\nicefrac k2$ of the estimations are greater than
      $(1+\epsilon)p$. Define $I_i$ to be the indicator random
      variable that takes value 1 if the $i$th trial exceeds $p$ by a
      factor of $1+\epsilon$. By definition, $\Pr{I_i = 1} \le
      \nicefrac14$. Then define $Y = \sum_{i=1}^k I_i$, $\Pr{X >
        (1+\epsilon) p} = \Pr{Y > \nicefrac k2}$. So
      \begin{align*}
        \Pr{X > (1+\epsilon) p} = \Pr{Y > \frac k2} &\le
        \binom{k}{\frac{k}{2}}
        \left(\frac{1}{4}\right)^{\nicefrac{k}{2}} \\
        &\le \left(\frac{ke}{\frac{k}{2}}\right)^{\nicefrac{k}{2}}
        \left(\frac{1}{4}\right)^{\nicefrac{k}{2}} \\
        &\le \left(\frac{e}{2}\right)^{\nicefrac{k}{2}}
      \end{align*}

      Now we want to ensure that this is less than $\delta$. So
      \begin{align*}
        %\Pr{X > (1+\epsilon) p} \le
        \left(\frac{e}{2}\right)^{\nicefrac{k}{2}} &\le \delta \\
        \frac{k}{2} \ln \frac{e}{2} &\le \ln \delta\\
        k &= \bigO{\log \delta}
      \end{align*}
    \end{subproblem}
  \end{problem}
\end{pset}

\end{document}
