\documentclass[11pt]{article}
\begin{document}
%%%%% written in LaTeX %%%
\addtolength{\oddsidemargin}{-1.25cm}
\addtolength{\textwidth}{3cm}
\addtolength{\textheight}{4cm}
\addtolength{\topmargin}{-2cm}
\newcommand{\een}{\end{enumerate}}
\newcommand{\noi}{\noindent}
\newcommand{\ra}{\rightarrow}
\newcommand{\sig}{\sigma}
\newcommand{\eps}{\epsilon}
\newcommand{\del}{\delta}
\newcommand{\Del}{\Delta}
\newcommand{\TREE}{\mbox{TREE}}
\newcommand{\co}{\mbox{COST}}
\newcommand{\lam}{\lambda}
\newcommand{\ah}{\alpha}
\newcommand{\gam}{\gamma}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bec}{\begin{center}}
\newcommand{\ece}{\end{center}}
\newcommand{\dis}{{\tt disc}}
\newtheorem{conjecture}{Conjecture}
\newtheorem{definition}{Definition}
\newtheorem{define}{Definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{claim}{Claim}[theorem]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{guess}[theorem]{Conjecture}
\bec {\Large\bf Rough Notes on Bansal's Algorithm}\\ Joel Spencer \ece
A quarter century ago I proved that given any $S_1,\ldots,S_n\subseteq
\{1,\ldots,n\}$ there was a coloring $\chi:\{1,\ldots,n\}\ra \{-1,+1\}$
so that $\dis(S_j)\leq 6\sqrt{n}$ for all $1\leq j\leq n$ where we
define \beq \label{defchi} \chi(S)=\sum_{i\in S}\chi(i) \eeq and $\dis(S)=|\chi(S)|$.
Here $6$ is an absolute constant
whose precise value will not here be relevant. The question remained: Is there
a polynomial time algorithm to find a coloring $\chi$ with this property.
I frequently conjectured that there was no such algorithm. But now Nikhil Bansal
has found one! His result (which has much more) can be found on ArXiv at
\bec http://arxiv.org/abs/1002.2259 \ece
Here I give a rough description, but emphasizing that the result is entirely
his.
\section{Semidefinite Programming}
At its core, Bansal's algorithm uses {\bf Semidefinite Programming}. Here
is the context:
Let $S_1,\ldots,S_m\subseteq \{1,\ldots,n\}$.
{\em Assume} that there {\em exists} a map
\[ \chi: \{1,\ldots,n\} \ra \{-1,0,+1\} \]
(such $\chi$ are called partial colorings and $i$ with $\chi(i)=0$ are called
uncolored) such that
\ben
\item At least $n\ah$ of the $i$ have $\chi(i)\neq 0$.
\item For $1\leq j\leq m$
\[ \dis(S_j) \leq \beta_j\sqrt{n} \]
\een
Consider the Semidefinite Program to find $\vec{v_1},\ldots,\vec{v_n}\in R^n$
satisfying (so this is a {\em feasibility} program):
\ben
\item $\vec{v_i}\cdot \vec{v_i} \geq 1$ for $1\leq i\leq n$.
\item $\sum_{i=1}^n \vec{v_i}\cdot\vec{v_i} \geq n\ah$
\item For $1\leq j\leq m$
\[ [\sum_{i\in S_j}\vec{v_i}]\cdot [\sum_{i\in S_j}\vec{v_i}] \leq [\beta_j\sqrt{n}]^2
\]
\een
The Semidefinite Program has a solution in $R^1$ by setting $\vec{v_i}=\chi(i)$.
Therefore, Semidefinite Programming will {\em find} a solution (though probably
not that one!) in time polynomial in $n,m$. Critically, we do {\em not}
need to know the original $\chi$. (Well, I'm lying a bit here. You need an $\eps$
of space -- that the conditions hold with $n\ah$ and $\beta_j\sqrt{n}$ replaced by
$n\ah(1+\eps)$ and $\beta_j\sqrt{n}(1-\eps)$ respectively for some fixed $\eps$.
This will always clearly hold.)
\section{My Result}
I need to state my result in more general form. For
completeness I give the argument, far better than my original proof, due to
Ravi Boppana. Let
\beq\label{defH} H(x) = -x\log_2x - (1-x)\log_2(1-x) \eeq
be the usual entropy function. For $\beta>0$ define
\beq\label{defcost} \co(\beta) = \sum_{i=-\infty}^{+\infty} -p_i\log_2p_i \eeq
with
\[ p_i = \Pr[i-\frac{1}{2}\leq \frac{N}{\beta} \leq i+\frac{1}{2}] \mbox{, $N$ standard normal}
\]
That is, $\co(\beta)$ is the entropy of the roundoff of $N$ to the nearest
multiple of $\beta$.
\begin{theorem} Let $S_1,\ldots,S_m\subseteq \{1,\ldots,n\}$. Let $\beta_1,\ldots,
\beta_m$ be such that
\beq\label{totalcost} \sum_{j=1}^m \co(\beta_j) \leq cn \eeq
where $c<1$. Write $c=1-H(\ah)$ with $\ah\in (0,\frac{1}{2})$. Then there
is a $\chi:\{1,\ldots,n\}\ra \{-1,0,1\}$ with
\ben
\item At least $2\ah n$ of the $i$ have $\chi(i)\neq 0$.
\item For $1\leq j\leq m$
\[ \dis(S_j) \leq \beta_j\sqrt{n} \]
\een
\end{theorem}
For completeness, here is Boppana's argument. For any $\chi:\{1,\ldots,n\}\ra
\{-1,+1\}$ set
\beq\label{defLam} \Lambda(\chi) = (b_1,\ldots,b_m) \eeq
where $b_j$ is the roundoff of $\chi(S_j)$ to the nearest multiple of $\beta_j\sqrt{n}$.
For $\chi:\{1,\ldots,n\}\ra \{-1,+1\}$ uniform random $\chi(S_j)$ is the sum
of $|S_j|$ random $\pm 1$ which is basically (minor hand waving here)
normal with mean zero and variance $|S_j|\leq n$ so that $b_j$ (fixed $j$,
$\chi$ random) will have entropy at most $\co(\beta_j)$. By subadditivity
$\Lambda(\chi)$ has entropy at most $\sum \co(\beta_j)=(1-H(\ah))n$.
Thus some value of $\Lambda(\chi)$ occurs with probability at least
$2^{-(1-H(\ah))n}$, that is, for at least $2^{H(\ah)n}$ different $\chi$.
A theorem of Dan Kleitman (weaker methods suffice if the best constants
are not needed) says that the subset of the Hamming Cube of a given size
with minimal diameter is basically a ball -- so that the diameter is at
least $2n\ah$. Take $\chi_1,\chi_2$ with $\Lambda(\chi_1)=\Lambda(\chi_2)$
that differ in at least $2n\ah$ places. Finally, set
\beq\label{beck} \chi(i) = \frac{\chi_1(i)-\chi_2(i)}{2} \eeq
Then $\chi(i)\in \{-1,0,+1\}$ tautologically and it is nonzero for at least $2n\ah$
values $i$. Critically, for every $j$, $\chi(S_j)=[\chi_1(S_j)-\chi_2(S_j)]/2$ and as
$\chi_1(S_j),\chi_2(S_j)$ have the same roundoff to the nearest multiple of $\beta_j\sqrt{n}$,
$|\chi(S_j)|\leq \beta_j\sqrt{n}$ as desired.
\noi {\tt Remark:} The jump from the ``small" entropy to $2^{H(\ah)n}$ different $\chi$
with the same $\Lambda(\chi)$ is basically the pigeonhole principle and led
me to the incorrect conjecture that this argument could not be made algorithmic.
\par For our purposes (as the constants do not concern us here) we need
only rough upper bounds on the function $\co(\beta)$. We note that
\beq\label{betasmall} \co(\beta)=\Theta(\ln \beta^{-1}) \mbox{ as } \beta\ra 0^+ \eeq
as, basically, usually $|N|\leq 10$ and so the roundoff of $N\beta$ usually takes
on one of $20\beta^{-1}$ values. Further
\beq\label{betabig} \co(\beta)=\Theta(\beta e^{-\beta^2/8}) \mbox{ as } \beta\ra +\infty \eeq
as, basically, we consider either $|N|\leq \beta/2$ or not, and the not
occurs with probability $\Theta(\beta^{-1}e^{-\beta^2/8})$. These are
far finer than we need, which is only that $\lim_{\beta\ra +\infty} \co(\beta)=0$
and that $\co(\beta)$ has very slow growth as $\beta\ra 0^+$. In application
we like to think of $\co(\beta_j)$ as the cost of the $j$-th discrepency
condition and (\ref{totalcost}) as our {\tt cost equation}.
The total cost is basically at most $n$. This allows
us to have a small number of quite tight (that is, $\beta_j$ small)
discrepency conditions.
\section{Floating Colors}
During the algorithm there for each vertex $1\leq i\leq n$ there will
be a value $x_i\in [-1,+1]$ which will move around.
Initially all
$x_i=0$ (though the method works for any initial $x_i$) and at the
end all $x_i\in \{-1,+1\}$. We call $i$ {\em floating} if
\[ |x_i| < 1 - \lg^{-1}n \]
Otherwise we call it {\em frozen}, and we call it {\em final} when
$x_i\in \{-1,+1\}$. We {\em never} have $|x_i| > 1$. Once $x_i$
is fixed it does not move until the very end, when we have the
(relatively easy) {\tt Final Roundoff} to the final values.
Suppose that during some period of the algorithm the values move
from $x_i$ to some $x_i'$. We let
\[ \Delta(S_j) = \sum_{i\in S_j} x_i'-x_i \]
denote the change in $\chi(S_j)$ during that period.
The algorithm splits into {\tt Phases}. We will number
them Phase $t$ for $t=0,1,\ldots$.
Phase $t$
will begin with $x_1,\ldots,x_n$ with at most $n2^{-t}$
floating. It will end with $x_1',\ldots,x_n'$ with at most
$n2^{-t-1}$ floating. (If it happens to start with fewer
than $n2^{-t-1}$ floating it does nothing.) Phase $0$ will have
\beq \label{phase0}
|\Delta(S_j)| \leq K\sqrt{n}, 1\leq j\leq n \eeq
and Phase $t\geq 1$ will have
\beq\label{phaset} |\Delta(S_j)| \leq K\sqrt{t}\sqrt{n2^{-t}}, 1\leq j\leq n \eeq
We'll end when the number of floating variables goes below $n\ln^{-1}n$,
and then do the Final Roundup.
I'll emphasize Phase $0$ here and make a few remarks about the
general case.
\section{The Easy Final Roundup}
{\em Suppose} that the phases have worked. From (\ref{phase0},\ref{phaset})
the total absolute value change in each $\chi(S_j)$ is at most the sum of the absolute
values of the changes and as $\sum_{t=1}^{\infty} \sqrt{t2^{-t}}$ converges
this is all $K_1\sqrt{n}$.
Now we have at most
$c\frac{n}{\ln n}$ floating $x_i$ and the rest frozen. For the
Final Roundup for each $i$ we replace $x_i$ with $+1$ with
probability $\frac{1+x_i}{2}$ and with $-1$ with probability
$\frac{1-x_i}{2}$. This keeps the expectation the same. Each
$\dis(S_j)$ is changed by $\sum_{i\in S_i}Y_i$ where
$\Pr[Y_i=1-x_i]=\frac{1+x_i}{2}$ and
$\Pr[Y_i=-1-x_i]=\frac{1-x_i}{2}$. Here $Y_i$ has mean zero
and variance $1-x_i^2$. This is at most $1$ for the at most
$cn\ln^{-1}n$ floating $i$ and at most $c\ln^{-1}n$ for the
at most $n$ frozen $i$ so the total variance is at most
$cn\ln^{-1}n$. Basic Chernoff bounds now give that the
probability that $\dis(S_j)$ is changed by more than $K_2\sqrt{n}$
is at most $n^{-c'}$. Adjusting the constants we make this
$o(n^{-1})$. So the Final Roundoff also changes each $\dis(S_j)$
by $O(\sqrt{n})$ and, putting everything together, the total
change overall in each $\dis(S_j)$ is at most $K_3\sqrt{n}$ as
desired.
\section{Phase $0$}
We start with floating $x_1,\ldots,x_n$ Actually they are all
zero but we needn't assume that and indeed its nicer not too
as this isn't the case with later phases. We proceed is
{\em steps}. At each step $x_i$ will move a small (more on
that soon) amount. When an $x_i$ becomes frozen it no longer
moves. When the number of floating variables reaches $n/2$ we
terminate Phase $0$. We are successful if (\ref{phase0}) holds
for all $S_j$. Our procedure may abort, we shall only show
that it succeeds with probability bounded away from zero.
Then if it aborts we simply repeat it and get a success with
an expected bounded number of attempts.
At the start of any step let
$FL$ denote the set of floating variables. Let $\Del(S_j)$
refer to the absolute value of the change in $\chi(S_j)$ up to
this point. We call $j$ {\em dangerous} if $\Del(S_j)\geq
\frac{K}{2}\sqrt{n}$ where our goal (\ref{phase0})
is that $\Del(S_j)\leq K\sqrt{n}$ at the end of Phase $0$.
More generally (a rather annoying technical part) we'll
call $j$ Level $l$ dangerous if $\Del(S_j)\geq K(1-2^{-l})\sqrt{n}$.
For technical reasons, we'll call the level of danger for $j$
the highest Level $l$ dangerous that has been reached during Phase $0$
up to this point. Let $DANG(l)$ denote those $j$ at level of danger $l$
and $SAFE$ denote the other $j$. We'll want to be more careful with the
dangerous $j$ by tightening the conditions.
While an infinite number of danger levels is technically
necessary it somewhat obscures the main line of the argument
and the reader can profitably think of a small proportion of
the $S_j$ becoming dangerous and having tighter conditions on
them.
At the start of the step we solve the Semidefinite Program
\ben
\item $\vec{v_i}\cdot \vec{v_i} \geq 1$ for $i\in FL$.
\item $\sum_{i=1}^n \vec{v_i}\cdot\vec{v_i} \geq n/4$
\item For $j\in SAFE$
\beq \label{savemove}
[\sum_{i\in S_j}\vec{v_i}]\cdot [\sum_{i\in S_j}\vec{v_i}] \leq [K_1\sqrt{n}]^2 \eeq
\item For $j\in DANG(l)$
\beq \label{dangmove} [\sum_{i\in S_j}\vec{v_i}]\cdot [\sum_{i\in S_j}\vec{v_i}] \leq [K_1\kappa_l\sqrt{n}]^2
\eeq
\een
We shall choose $K_1$ large and then $K$ much larger by (\ref{setK}), both absolute constants.
Here the $\kappa_l$ will be chosen by (\ref{setkappa}) to go to zero at an appropriate rate to
be discussed later. It may be that the Semidefinite Program above does not
find a solution. In this case we say that we {\em abort} the attempt at Phase 1.
Since Semidefinite Programming (allowing some $\eps$ leeway) will find some
solution if it exists this will only occur if the Semidefinite Program does
not have a solution. More on this later.
\noi {\bf Central Step:} We let $g_1,\ldots,g_n$ be i.i.d. standard normals and set
$\vec{G}=(g_1,\ldots,g_n)$. We set
\beq\label{change} \del_i = \eps \vec{v_i}\cdot \vec{G} \eeq
with $\eps$ chosen below (\ref{seteps}). We update:
\beq\label{update} x_i \leftarrow x_i + \del_i \eeq
for $1\leq i\leq n$.
As $\vec{G}$ is distributed symmetrically, $\del_i$ will be
normally distributed with mean zero and standard deviation
$\eps|\vec{v_i}|\leq \eps$ We set
\beq\label{seteps} \eps = c\ln^{-3/2}n \eeq
Then the probability that $|\del_i| \geq \ln^{-1}n$ is
polynomially small and it will not occur throughout the
procedure. Therefore the $x_i$ will not jump over the
values $-1$ or $+1$. (The algorithm would work for
smaller $\eps$ but smaller $\eps$ would require more
steps as indicated below.)
\begin{claim} The probability that this process goes
$S$ steps (or more) is at most $4\eps^{-2}S^{-1}$.
\end{claim}
Proof: Define $W_t$ to be the value of $\sum_{i=1}^n x_i^2$
if the process is still going. Letting $x_1,\ldots,x_n$ be
the values after $t-1$ steps,
\beq \label{expchange} E[W_t-W_{t-1}] = \sum_{i=1}^n E[(x_i+\del_i)^2-x_i^2] \eeq
But as $\del_i$ is normal with mean zero and variance $\eps^2|\vec{v_i}|^2$ we get
\beq \label{expchange1} E[W_t-W_{t-1}] = \sum_{i=1}^n E[\del_i^2]= \sum_{i=1}^n \eps^2|\vec{v_i}|^2 \geq
\frac{n}{4}\eps^2 \eeq
If the process has already stopped we simply set
$W_t=W_{t-1}+\frac{n}{4}\eps^2$. With this technical trick, $W_0,\ldots,W_S$ are defined
and
\beq \label{aa1} E[W_S] \geq S\eps^2\frac{n}{4} \eeq
If the process does stop then at the time $t$ that it does start $W_t\leq n$ tautologically
and hence the final
\beq \label{aa2} W_S \leq n +(S-t)\eps^2\frac{n}{4} \leq n + S\eps^2\frac{n}{4} \eeq
If the process has not stopped by time $S$ then all $|x_i|\leq 1$ and
\beq \label{aa3} W_S \leq n \eeq
Let $p$ be the probability that the process has not stopped by time $S$. Then
\beq \label{aa4} S\eps^2\frac{n}{4}\leq E[W_S]\leq pn + (1-p)[n+S\eps^2\frac{n}{4}] \eeq
from which the claim follows.
Now we simply set
\beq\label{setS} S = 40 \eps^{-2} \eeq
so that with 90\% chance the process has stopped in $S$ stops.
If the process has not stopped it is considered a failure. Henceforth
we consider the process continuing for at most $S$ steps.
We now need ``only" show that, with the appropriate values of $\kappa_l$,
the Semidefinite Programs will all have solutions with probability, say,
50\%.
Consider a single $S_j$ and the movement of $\dis(S_j)$ throughout Phase 0.
At each step this is changed by the sum of the changes of the $x_i$, $i\in S_j$,
which is precisely
\beq \label{changeSj} \eps \vec{G}\cdot [\sum_{i\in S_j} \vec{v_i}] \eeq
The change is normally distributed with mean zero and standard deviation $\eps$
times the norm of $\sum_{i\in S_j} \vec{v_i}$. From (\ref{savemove},\ref{dangmove})
we have:
\ben
\item While $S_j$ is safe the change in $\dis(S_j)$ is normally distributed with
mean zero and standard deviation at most $K_1\eps\sqrt{n}$.
\item While $S_j$ is at danger level $l$ the change in $\dis(S_j)$ is normally distributed with
mean zero and standard deviation at most $K_1\kappa_l\eps\sqrt{n}$.
\een
Now we can bound the probability that $S_j$ becomes dangerous. There are at most
$S=40\eps^{-2}$ steps and at each step the change is normal with mean zero and
standard deviation at most $K_1\eps\sqrt{n}$. The values of $\dis(S_j)$ become
a martingale. The $\eps$ scales out and the probability of reaching $\frac{K}{2}\sqrt{n}$
is at most $2\exp[-K^2/(160K_1^2)]$. We'll pick $K$ so large, for definiteness we
will set
\beq \label{setK} K=20K_1 \eeq
so that this probability is quite small, less than $2\exp[-2K_1^2]$.
Lets look at the probability that $S_j$ becomes $l+1$-dangerous. Once it is
$l$-dangerous each step is normal with mean zero and standard deviation at most
$K_1\kappa_l\eps\sqrt{n}$. It has to move at least $K2^{-l-1}\sqrt{n}$. Even
it has all $S$ steps (so we are giving some ground here, indeed, ignoring the
probability that it becomes $l$-dangerous) the probability is at most
$2\exp[-K^22^{-2l-2}\kappa_l^{-2}/160K_1^2]$. For definiteness, we set
\beq\label{setkappa} \kappa_l = 4^{-l} \eeq
so that this probability goes rapidly to zero, less than $2\exp[-2K_1^22^{2l-2}]$.
We {\em cannot} assume that the walks for the different $S_j$ are independent.
If, for example, $S_j=S_{j'}$ then the two walks would be precisely the same.
Nonetheless, the above probabilities are so small that we can effectively use
Markov's Inequality. The probability that the number of $j$ for which $S_j$
becomes $l+1$-dangerous is greater than $2^{l+3}\exp[-2K_1^22^{2l-2}]$.
is at most $2^{-l-2}$. Adding over $l\geq 0$, with probability at least
50\% this does not occur for any $l\geq 0$.
This combines with our previous at least 90\% chance that the process does not
go to $S$ steps. Thus with a positive, here 40\%, chance, Phase I is successful.
Or is it? We must check that the Semidefinite Program will be feasible.
To do that we must check that the cost equation (\ref{totalcost})
is satisfied with $c=1-H(1/8)$. Here there are at most $n$ conditions
of cost $\co[K_1]$ and for each $l\geq 0$ at most
$n2^{l+3}\exp[-2K_1^22^{2l-2}]$ conditions of cost $\co[K_14^{1-l}]$.
That is, the cost equation becomes
\beq\label{costa} n\co[K_1]+\sum_{l\geq 0}
n2^{l+3}\exp[-2K_1^22^{2l-2}]\co[K_14^{1-l}] \leq cn \eeq
The factors of $n$ scale out and this becomes
\beq\label{costb} \co[K_1]+\sum_{l\geq 0}
2^{l+3}\exp[-2K_1^22^{2l-2}]\co[K_14^{1-l}] \leq c \eeq
We could easily give an explicit $K_1$ here but let us
instead show that (replacing $K_1$ by $x$)
\beq\label{costc} \lim_{x\ra\infty}\co[x]+\sum_{l\geq 0}
2^{l+3}\exp[-2x^22^{2l-2}]\co[x4^{1-l}] = 0 \eeq
Clearly $\lim_{x\ra\infty} \co[x]=0$.
The only difficulty is that for any fixed $x$, $\co[x4^{1-l}]$
is unbounded. But its growth rate is slow. With $x\geq 4$
we have from (\ref{betasmall})
\beq\label{costd} \co[x4^{1-l}] \leq \co[4^{-l}] \leq c_1(l+1) \eeq
for some constant $c_1$, uniformly over $l\geq 0$.
Thus it suffices that
\beq\label{coste} \lim_{x\ra\infty}\sum_{l\geq 0}
(l+1)2^{l+3}\exp[-2x^22^{2l-2}] =0 \eeq
which is clearly true. That is, there is a constant $K_1$ with
(\ref{costa}) holding. For this $K_1$, Phase 1 has at least a
40\% chance of succeeding.
{\tt Remark:} A worry throughout is that we start with $n$ sets and
so some of them will get into deep trouble. The cost equation
(\ref{totalcost}) allows some equations to be in trouble. But the
cost of being level $l$ dangerous only goes up linearly in $l$ and
the proportion of sets reaching that level drops hypergeometrically
in $l$ and so the cost equation remains satisfied.
\section{ A few words on later Phases}
{\em If} we had $n2^{-t}$ floating variables and $n2^{-t}$ sets
we would only have a change of parameter and our algorithm for
Phase $t$ would give all $\dis(S_j)\leq K_1(n2^{-t})^{1/2}$.
The technical issue is that we still have $n$ sets and this
leads to an additional $\sqrt{t}$ term. But there is plenty
of room, we could even replace the $\sqrt{t}$ by, say, $2^{t/6}$,
finding the weaker $\dis(S_j)\leq K_1\sqrt{n}2^{-t/3}$ but still
getting the final discrepancy as $O(\sqrt{n})$.
In the safe region with $n$ sets and $n2^{-t}$ floating vertices
we replace condition (\ref{savemove}) with
\beq \label{savemove1}
[\sum_{i\in S_j}\vec{v_i}]\cdot [\sum_{i\in S_j}\vec{v_i}] \leq [K_1\sqrt{t}\sqrt{n2^{-t}}]^2 \eeq
Now in the cost equation (\ref{totalcost}) has $m=n$ sets and
all $\beta_i=K_1\sqrt{t}$. From (\ref{betabig})
$\co(K_1\sqrt{t})=\exp[-\Theta(tK_1^2)]$. For $K_1$ appropriately
large this is much smaller than $2^{-t}$ and so
\beq\label{totalcost1}
\sum_{i=1}^n \co(\beta_i) \leq cn \eeq
For the full argument we must again consider $S_j$ to be dangerous
at level $l$ when $\dis(S_j)$ reaches $K(1-2^{-l})\sqrt{t}\sqrt{n2^{-t}}$
at which point the bound on $|\vec{v_j}|$ is tightened by a factor
of $\kappa_l$. The details are very similar to the Phase $0$ case and
I omit them.
\end{document}