\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CSG399}{Algorithmic Power Tools}{Fall 2007}{26 November 2007}{4}

\begin{center}
\Large{\bf Problem Set 3 (due Friday, December 14)}
\end{center}

\noindent {\bf Grading.}  This problem set has a total of 100 points.
All the problems concern specific problems we covered in the lectures.
From a grading perspective, the total points allocated for problem
sets is 200 points.  So you should plan on attempting at least 200
points in all, over all problem sets.  Any score you earn beyond the
basis of 200 points will be bonus points for you.

\noindent {\bf Collaboration.} You are welcome to collaborate on
solving these problems.  But you must write the solutions on your own.
Please cite any collaborators and/or references that help you in
arriving at your solutions.

{\bf 1. (15 points) Local improvement algorithm for Max-Cut} 

Recall that in the Max-Cut problem, we are given an undirected graph
$G = (V, E)$ and we would like to partition the vertices into two sets
$V_1$ and $V_2$ so as to maximize the number of edges with one
end-point in $V_1$ and the other end-point in $V_2$.  In this
exercise, we consider a simple local improvement algorithm for the
problem discussed in class.
  
Initially, partition the vertices arbitrarily.  Consider the following
local improvement step.  Pick a node $u$, say in $V_1$, that has fewer
edges to vertices in $V_2$ than to other vertices in $V_1$; if such a
node $u$ exists, then move $u$ from $V_1$ to $V_2$.

The local improvement algorithm executes the above step as long as
there exists a node that has fewer edges in the cut than edges to
other vertices in its set.
  
Prove that the above algorithm is a polynomial-time 2-approximation
algorithm for Max-Cut.

{\bf 2. (15 points) Capacity of a binary erasure channel}

Consider an erasure channel in which an input bit (0 or 1) is erased
(output as '?') by the channel independently with probability $p$.
What is the capacity of this channel?

{\bf 3. (15 points) Supermultiplicative and submultiplicative
functions}

Let $f$ be a function mapping positive integers to positive reals.  We
say that $f$ is supermultiplicative if $f(m + n) \ge f(m) \cdot f(n)$,
and submultiplicative if $f(m + n) \le f(m) \cdot f(n)$.  Prove that
if $f$ is supermultiplicative, then
\[
\sup_n f(n)^{1/n} = \lim_{n \rightarrow \infty} f(n)^{1/n}.
\]
Prove that if $f$ is submultiplicative, then
\[
\inf_n f(n)^{1/n} = \lim_{n \rightarrow \infty} f(n)^{1/n}.
\]
You may assume that $f(n)^{1/n}$ is bounded; that is, there exists
a real $M$ such that for any positive integer $n$, $f(n)^{1/n} \le M$.

We used the above two facts for establishing that the fractional
chromatic number of a graph is equal to the fractional clique number.

{\bf 4. (15 points) Embedding a hypercube in a sphere} 

Consider an embedding of the $2^k$-point hypercube in the
$k$-dimensional sphere.  Show that any angle formed by three points of
the hypercube is at most 90 degrees.

{\bf 5. (15 points) Random vector in high dimensions} 

Let $r$ be a unit vector, chosen uniformly at random from an
$m$-dimensional unit sphere.  Prove the following two inequalities.

\begin{eqnarray*}
\Pr\left[|r \cdot e_z| < \frac{t}{\sqrt{m}}\right] & \le & \Theta(t)\\
\Pr\left[|r \cdot e_z| > \frac{t}{\sqrt{m}}\right] & \le &
e^{-\Theta(t^2)}.
\end{eqnarray*}

{\bf 6. (25 points) Conditions in the Master Structure Theorem }

The Master Structure Theorem (in Arora-Rao-Vazirani's sparsest cut
result) says that given $n$ points $v_1, \ldots, v_n$, in $\Real^m$
such that (a) the average $\ell_2^2$ distance among them is
$\Omega(1)$, (b) the $\ell_2^2$ distances form a metric, and (c)
$||v_i|| \le 1$, there exist subset $S$ and $T$ of the points such
that $|S| = \Omega(n)$, $|T| = \Omega(n)$ and $d(S,T) =
\Omega(1/\sqrt{\log n})$.

Show that the desired claim does not hold if any of the three
conditions is dropped.

\junk{
If not (a), can put all points in one position.  If not (c), then put
one point far away from the rest.
}
\end{document}

