% LATEX NOTES:  
%  *    Use ~ between two words to prohibit a line break at that point.
%  *    Multiletter Pascal variable names should be put in text italic, 
%       like this: \id{var\_name}.

% TO INCREASE BASELINESKIP BY 2pt:
% \addtolength{\baselineskip}{2pt}
% TO SET BASELINESKIP TO 12pt:
% \setlength{\baselineskip}{12pt}
% TO MAKE BASELINESKIP SLIGHTLY SMALLER:
% \setlength{\baselineskip}{0.95\baselineskip}



% *************************************
% FORMATTING IDENTIFIER NAMES
% *************************************

\DeclareOldFontCommand{\rm}{\normalfont\rmfamily}{\mathrm}
\DeclareOldFontCommand{\sf}{\normalfont\sffamily}{\mathsf}
\DeclareOldFontCommand{\tt}{\normalfont\ttfamily}{\mathtt}
\DeclareOldFontCommand{\bf}{\normalfont\bfseries}{\mathbf}
\DeclareOldFontCommand{\it}{\normalfont\itshape}{\mathit}
\DeclareOldFontCommand{\sl}{\normalfont\slshape}{\@nomath\sl}
\DeclareOldFontCommand{\sc}{\normalfont\scshape}{\@nomath\sc}


% Write multichar identifier names using \id in either mathmode or text;
% For ex, $\id{high}(x)$ is an expression using the \id{high} function.
% Use ``\ '' if a space is desired, as in math mode.
\def\id#1{\ensuremath{\mathit{#1}}}
\let\idit=\id
\def\idbf#1{\ensuremath{\mathbf{#1}}}
\def\idrm#1{\ensuremath{\mathrm{#1}}}
\def\idtt#1{\ensuremath{\mathtt{#1}}}
\def\idsf#1{\ensuremath{\mathsf{#1}}}
\def\idcal#1{\ensuremath{\mathcal{#1}}}  % Use with capital letter args only


% *************************************
% BOLD MATH IN SECTION HEADERS
% *************************************

\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus-1ex minus
    -.2ex}{2.3ex plus.2ex}{\reset@font\Large\bf\boldmath}}
\def\subsection{\@startsection{subsection}{2}{\z@}{-3.25ex plus-1ex
    minus-.2ex}{1.5ex plus.2ex}{\reset@font\large\bf\boldmath}}
\def\subsubsection{\@startsection{subsubsection}{3}{\z@}{-3.25ex plus
    -1ex minus-.2ex}{1.5ex plus.2ex}{\reset@font\normalsize\bf\boldmath}}
\def\paragraph{\@startsection
%    {paragraph}{4}{\z@}{3.25ex plus1ex minus.2ex}{-1em}{\reset@font
    {paragraph}{4}{\z@}{3ex plus1ex minus.2ex}{-1em}{\reset@font
    \normalsize\bf\boldmath}}
\def\subparagraph{\@startsection
%    {subparagraph}{4}{\parindent}{3.25ex plus1ex minus
    {subparagraph}{4}{\parindent}{3ex plus1ex minus
     .2ex}{-1em}{\reset@font\normalsize\bf\boldmath}}


% *************************************
% SPACING
% *************************************

\let\origparskip=\parskip
\lineskiplimit=0pt
\lineskip=0pt
\tolerance=5000

% Eliminate excessive space before paragraphs
\def\paragraph{\@startsection
     {paragraph}{4}{\z@}{1.5ex plus .2ex}{-1em}{\normalsize\boldmath\bf}}
\def\subparagraph{\@startsection
     {subparagraph}{4}{\parindent}{1.5ex plus .2ex}{-1em}{\normalsize\boldmath\bf}}
%\setlength{\partopsep}{0pt}

\def\sectionfilbreak{\vskip 0pt plus.20\textheight\penalty-250
  \vskip 0pt plus-.20\textheight}         % formerly .3 on both lines

\def\filbreak{\par\vfil\penalty-200\vfilneg}

\newbox\tallstrutbox
\setbox\tallstrutbox=\hbox{\vrule height12pt depth 3.5pt width0pt}
\def\tallstrut{\relax\ifmmode\copy\tallstutbox\else\unhcopy\tallstrutbox\fi}
\newbox\tallerstrutbox
\setbox\tallerstrutbox=\hbox{\vrule height14pt depth 3.5pt width0pt}
\def\tallerstrut{\relax\ifmmode\copy\tallerstutbox\else\unhcopy\tallerstrutbox\fi}

% *****************************
% COMMENTS
% *****************************

%% Macro for writing in the margin comments on what is left to be done.
%% Use \withcomments in the preamble if you want comments to appear.
\def\comment#1{}
\def\ournote{\comment}
\def\withcomments{
\addtolength{\oddsidemargin}{-0.5 in}
\addtolength{\evensidemargin}{-0.5 in}
\newcounter{mycommentcounter}
\def\comment##1{\refstepcounter{mycommentcounter}%
  \ifhmode%
  \unskip%
  {\dimen1=\baselineskip \divide\dimen1 by 2 %
    \raise\dimen1\llap{\tiny -\themycommentcounter-}}\fi%
  \marginpar{\renewcommand{\baselinestretch}{0.8}%
    \footnotesize [\themycommentcounter]: \raggedright ##1}}
\date{\framebox{Draft of \today}}
}

%% OLD STUFF:
%% Set \marginparwidth to ensure comment does not runs off the end of
%% the page.  
%\setlength{\marginparwidth}{8.5in}
%\addtolength{\marginparwidth}{-1.0in}
%\addtolength{\marginparwidth}{-\oddsidemargin}
%\addtolength{\marginparwidth}{-\textwidth}
%\addtolength{\marginparwidth}{-2.0\marginparsep} 
%% To get the same space on both sides of the margin text
%% because duke printers use weird margins:
%\addtolength{\marginparwidth}{-0.125in}
%\newcounter{mycomments}
%\def\comment##1{\refstepcounter{mycomments}%
%\ifhmode%
%\unskip%
%{\dimen1=\baselineskip \divide\dimen1 by 2 %
%\raise\dimen1\llap{\tiny -\themycomments-}}\fi%
%\marginpar{\tiny [\themycomments]: ##1}}%


% *************************************
% ENVIRONMENTS AND THEOREM-LIKE FORMATS
% *************************************

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}
\newtheorem{conjecture}{Conjecture}
\newtheorem{fact}{Fact}
\newtheorem{claim}{Claim}

\newtheorem{JSVdef}{Definition}
\newenvironment{definition}{\begin{JSVdef}\em}{\end{JSVdef}}

\newtheorem{JSVremark}{Remark}
\newenvironment{remark}{\begin{JSVremark}\em}{\end{JSVremark}}

\newtheorem{JSVex}{Example}
\newenvironment{example}{\begin{JSVex}\em}%
{\unskip\nobreak\hskip 1em plus 1fil\nobreak$\Box$
\parfillskip=0pt 
%{\unskip\nobreak\quad\nobreak \blackslug
\end{JSVex}}

% This defines the \cramped macro, which reduces whitespace around \items
\def\cramped                                    % "Cramped" list style.
  {\parskip\@outerparskip\@topsep\parskip       % put after \begin{itemize}
  \@topsepadd2pt\itemsep0pt                     %
%  \settowidth{\labelwidth}{\@itemlabel}                %
%  \advance\leftmargin-\labelsep                        %
%  \advance\leftmargin-\labelwidth              %
%  \advance\@totalleftmargin-\leftmargin                %
%  \advance\linewidth\leftmargin                        %
%  \parshape1\@totalleftmargin\linewidth                %
}

% The compactlist environment has \parskip set to the original \parskip
\newenvironment{compactlist}{\begin{list}{}{\setlength{\parsep}{\origparskip}%
\setlength{\itemsep}{0pt}}}{\end{list}}

% The problem environment is for formatting things like problem definitions,
%   with unindented title, followed by hanging indents for instance and question.
\newenvironment{problem}{\begin{compactlist}\item[]\hskip-\leftmargin\nopagebreak
  \ignorespaces}{\end{compactlist}}

% This can be used for claims or unnumbered theorems
\newenvironment{nonnumberedtheorem}[1]{\begin{trivlist}\item[]{\bf #1\/} 
  \em\ignorespaces }{\end{trivlist}}

\newenvironment{varlabellist}[1]{\begin{list}{}{\settowidth{\labelwidth}{#1}%
\settowidth{\leftmargin}{#1\hskip\labelsep}}}{\end{list}}

% The proof environment.  For proofs that don't start with ``Proof:''
%   use the proofarg environment with the desired start as argument
\newenvironment{proof}{\trivlist\item[]\emph{Proof}:}%
{\unskip\nobreak\hskip 1em plus 1fil\nobreak$\Box$
\parfillskip=0pt%
\endtrivlist}
\newenvironment{proofsketch}{\trivlist\item[]\emph{Proof Sketch}:}%
{\unskip\nobreak\hskip 1em plus 1fil\nobreak$\Box$
\parfillskip=0pt%
\endtrivlist}
\newenvironment{proofarg}[1]{\trivlist\item[]\emph{#1}:}%
{\unskip\nobreak\hskip 2em plus 1fil\nobreak$\Box$
\parfillskip=0pt%
\endtrivlist}
\newenvironment{proofof}[1]{\trivlist\item[]{\em Proof of #1\/}:}%
{\unskip\nobreak\hskip 2em plus 1fil\nobreak$\Box$
\parfillskip=0pt%
\endtrivlist}


%% Old way of doing proofs (without an environment)
%\newcommand{\qed}{\quad\rule[-1.5pt]{4.5pt}{9pt}\ifmmode\else\par\addvspace\topsep\fi}
%\newcommand{\startproof}{\par\addvspace\topsep\noindent{\em Proof\/}: \ignorespaces }
%\newcommand{\startproofarg}[1]{\par\addvspace\topsep\noindent {\em #1\/}: \ignorespaces }

%%\newcounter{algorithm}
%\def\thealgorithm{\@arabic\c@algorithm}
%\def\fps@algorithm{tbp}
%\def\ftype@algorithm{1}
%\def\ext@algorithm{lof}
%\def\fnum@algorithm{Algorithm \thealgorithm}
%\def\algorithm{\@float{algorithm}}
%\let\endalgorithm\end@float
%\@namedef{algorithm*}{\@dblfloat{algorithm}}
%\@namedef{endalgorithm*}{\end@dblfloat}


%% this environment defines a minipage so that all text inside is kept
%% in one page. useful for putting algorithms in so that they don't run
%% across pages.
\newenvironment{keepinpage}{\medskip
\begin{minipage}{\textwidth}}{\end{minipage}\par\medskip}


% *****************
% BIBTEX MODS
% *****************
 
% Special redefinition hack so that chapter or section header not put in
% explicitly by \begin{thebibliography} 
% Not needed when using TiB
\def\thebibliography#1{\list
  {\@biblabel{\arabic{enumiv}}}{\settowidth\labelwidth{\@biblabel{#1}}%
    \leftmargin\labelwidth
    \advance\leftmargin\labelsep
    \usecounter{enumiv}%
    \let\p@enumiv\@empty
    \def\theenumiv{\arabic{enumiv}}}%
    \def\newblock{\hskip .11em plus.33em minus.07em}%
    \sloppy\clubpenalty4000\widowpenalty4000
    \sfcode`\.=\@m}%


% *****************
% MISC MATH SYMBOLS
% *****************
 
\font\manual=manfnt % font used for the METAFONT logo, etc.
\def\tickmark{\manual\char'170\rm\kern.15em}% solid triangle pointing right

\def\BiBTeX{B\textsc{ib}\TeX}

\def\boxit#1{\vbox{\hrule\hbox{\vrule\kern3pt
  \vbox{\kern3pt#1\kern3pt}\kern3pt\vrule}\hrule}}

\def\Box{\boxit{\null}}

\def\blackslug{\penalty5000\hbox{\normalsize\rm\hskip.2em
     \vrule width.4em height1.6ex depth.4ex \hskip.2em}}

\newcommand{\notuparrow}{\skew{-4}\not\uparrow}
\def\asympt{\sim}

\def\leqsim{\mathrel{\lower2.3pt\hbox{$\mathpalette\oversim<$}}}
\def\geqsim{\mathrel{\lower2.3pt\hbox{$\mathpalette\oversim>$}}}
\def\oversim#1#2{\lower.2pt\vbox{\baselineskip0pt\lineskip-.5pt
  \ialign{$\mathsurround=0pt #1\hfill##\hfil$\crcr#2\crcr\sim\crcr}}}

\def\sqr#1#2{{\vcenter{\hrule height.#2pt
      \hbox{\vrule width.#2pt height#1pt \kern#1pt
         \vrule width.#2pt}
      \hrule height.#2pt}}}
\def\square{\mathchoice\sqr34\sqr34\sqr{2.1}3\sqr{1.5}3}

\def\Omegait{\mathit{\Omega}}
\def\Thetait{\mathit{\Theta}}
\def\ex{\mathrm{E}}
\def\Vary{\mathop{\mathrm{Var}}}
\def\Prob{\mathop{\mathrm{Prob}}}
\def\polylog{{\mathop{\mathrm{polylog}}\nolimits}}

% *****************
% Miscellaneous
% *****************

%\def\jsvcopyright{{\ooalign
%  {\hfil\raise.07ex\hbox{c}\hfil\crcr\mathhexbox20D}}}
\def\jsvcopyright{{\ooalign
  {\mathhexbox20D\crcr{\hfil\raise.07ex\hbox{c}\hfil}}}}
\def\blankchar{\leavevmode\hbox{\tt\char`\ }} % visible blank space char
\def\tildechar{\~{}}         % or \chardef\tildechar="7E
\def\naive{na\"\i ve}
\def\Naive{Na\"\i ve}
\def\role{r\^ ole}
\def\frlquote{\vbox{\offinterlineskip
  \hbox{${\scriptscriptstyle\langle\!\langle}$}\kern-0.1pt}\hskip
  -.6pt plus.3pt minus.2pt~}
\def\frrquote{~\hskip -.6pt plus.3pt minus.2pt\vbox{\offinterlineskip
  \hbox{$\scriptscriptstyle\rangle\!\rangle$}\kern-0.1pt}}

\def\smashit#1{{\smash{#1} \vphantom V}}
\def\smashsqrt#1{\sqrt{\smash{#1} \vphantom V}}

% *****************
% Figure parameters
% *****************

% Using the graphics package
% use \upfig{foo} to include a postscript file foo.ps
\newcommand{\upfig}[1] {\centerline{\scalebox{\scalefig}{\includegraphics{#1}}}}

% For use with combined LaTeX/postscript figures produced by xfig
\newcommand{\centerfig}[1]{%
  \vspace*{\fill}

  \hspace*{\fill}\hspace{-1 in}%
  \input{#1}%
  \hspace{-1 in}\hspace*{\fill}

  \vspace*{\fill}}

\setcounter{topnumber}{6}
\renewcommand{\topfraction}{1}
\setcounter{bottomnumber}{6}
\renewcommand{\bottomfraction}{1}
\setcounter{totalnumber}{8}
\renewcommand\textfraction{0}
\renewcommand{\floatpagefraction}{1}
\setcounter{dbltopnumber}{2}
\renewcommand\dbltopfraction{1}
\renewcommand\dblfloatpagefraction{1}

% ***************
% USEFUL COMMANDS
% ***************

\def\smallskip{\addvspace{\smallskipamount}}
\def\medskip{\addvspace{\medskipamount}}
\def\bigskip{\addvspace{\bigskipamount}}


% ****************
% PROGRAM KEYWORDS
% ****************

\def\bcom{$\{$}
\def\ecom{$\}$}
\def\bbegin{\idbf{begin}}
\def\bend{\idbf{end}}
\def\bendif{\idbf{endif}}
\def\benddo{\idbf{enddo}}
\def\bfor{\idbf{for}}
\def\bto{\idbf{to}}
\def\bwhile{\idbf{while}}
\def\bdo{\idbf{do}}
\def\bif{\idbf{if}}
\def\bthen{\idbf{then}}
\def\belse{\idbf{else}}
\def\bprogram{\idbf{program}}
\def\bprocedure{\idbf{procedure}}
\def\brepeat{\idbf{repeat}}
\def\breturn{\idbf{return}}
\def\bbreak{\idbf{break}}
\def\bnil{\idbf{nil}}
\def\buntil{\idbf{until}}
\def\bforever{\idbf{forever}}
\def\bfalse{\idbf{false}}
\def\btrue{\idbf{true}}
\def\iwrite{\id{write}}
\def\iwriteln{\id{writeln}}

