%% example.tex.1.0:Typesetting Guide for``Theory of Computing'' August 4, 2005
%  (c) Alexander Russell, Theory of Computing 2005
%----------------------------------------------------------------------
%% Requires toc.cls in a directory that will be searched by 
%% LaTeX (LaTeX will automatically search the directory in 
%% which example.tex appears). Requires petersen.eps to 
%% produce .dvi (or .ps) output; requires petersen.pdf to 
%% produce .pdf output.
%----------------------------------------------------------------------

\documentclass{toc}
\usepackage{graphicx}
\usepackage{verbatim}

\tocdetails{%
   volume=0, number=5, year=2005, firstpage=78,
   received={October 15, 2004}, 
   published={December 31, 2004}
}

\theoremstyle{plain}
\newtheorem{idea}[theorem]{Idea}
%\newtheorem{idea}{Idea}[section]

\theoremstyle{definition}
\newtheorem{thought}[theorem]{Thought}
%\newtheorem{thought}{Thought}[section]

\DeclareMathOperator{\cov}{\textsf{Cov}}


\runningauthor{\begin{minipage}{.9\textwidth}\centering A. Russell,
    J. Milestone, K. Sz\H{o}l\H{o}ssy,
    L. Sz\H{o}l\H{o}ssy,\\ M. Sz\H{o}l\H{o}ssy, N. Sz\H{o}l\H{o}ssy,
    O. Sz\H{o}l\H{o}ssy\end{minipage}}
\runningtitle{Typesetting guidelines}
\copyrightauthor{Alex Rusell and the extremely unnecessaily 
large ficticious family of authors}

\begin{document}

\begin{frontmatter}[classification=text]
\title{Typesetting Guidelines for the\\ \textsl{Theory of Computing}}
\tocpdftitle{Typesetting guidelines}
\tocpdfauthor{Alex Russel et. al.}

\author[alex]{Alexander Russell\thanks{Supported by GGA Grant \#
142857.}}%
\author[john]{John C. Milestone\thanks{Fictitious name to %
demonstrate format.}}%
\author{K\'alm\'an Sz\H{o}l\H{o}ssy\thanks{Another fictitious
name.}}
\author{L\'aszl\'o Sz\H{o}l\H{o}ssy\thanks{Another member of a large
fictitious family to illustrate what happens when a paper has many
authors.}}%
\author{ M\'aria Sz\H{o}l\H{o}ssy}
\author{N\'andor Sz\H{o}l\H{o}ssy}
\author{Orb\'an Sz\H{o}l\H{o}ssy}

\tockeywords{Theory of Computing, Guidelines}

\begin{abstract}
  This document describes \LaTeX\ typesetting guidelines for the
  \emph{Theory of Computing}, including the use of the
  \texttt{toc.cls} class file.
\end{abstract}

\tocams{None}

\tocacm{None}

\end{frontmatter}

\section{Introduction}

This document describes typesetting guidelines for the \emph{Theory
of
  Computing}. Articles for \emph{Theory of Computing} are to be
typeset in \LaTeX, using the \texttt{toc.cls} class file. The most
recent version of the class file (and this explanatory document) may
be found at
\begin{center}
  \url{http://theoryofcomputing.org}\enspace.
\end{center}

\begin{sloppypar}
The \texttt{toc.cls} class file requires \LaTeX2e and the AMS-\LaTeX\
packages \texttt{amsmath}, \texttt{amssymb} and \texttt{amsthm} (all
of which are included in the AMS-\LaTeX\ distribution). The
AMS-\LaTeX\ distribution is a part of many \LaTeX\ distributions
(e.g., Te\TeX, Mik\TeX, \&c.) and is freely available from the 
American Mathematical Society at
\begin{center}
 \url{http://www.ams.org/tex/amslatex.html}\enspace.
\end{center}
In addition, the \texttt{toc.cls} file requires the following
packages, all of which are available from the comprehensive \TeX\
archive network (\url{http://www.ctan.org/}): \texttt{color},
\texttt{eucal}, \texttt{refcount}, 
\texttt{lastpage} and \texttt{hyperref}. Most \LaTeX\ installations
will have these package installed by default.
\end{sloppypar}

As a general rule, please minimize use fancy \LaTeX\ code or 
inclusion of esoteric packages.

\section{Preamble, title, and author data}

Your file should begin with
\begin{verbatim}
\documentclass{toc}
\end{verbatim}

Following this, invoke the commands \verb`\runningauthor` and
\verb`\runningtitle` to set the running author and title information
for the headers, as below:

\begin{verbatim}
\runningauthor{First Author, Second Author, Third Author}
\runningtitle{Typesetting Guidelines for ToC}
\end{verbatim}

Then use the \verb`\copyrightauthor` command to set the copyright string
in the
footer of the title page. For example

\begin{verbatim}
\copyrightuthor{First Author, Second Author, Third Author}
\end{verbatim}

Next, invoke the \verb'\begin{document}' command followed by the
  \verb'frontmatter' declaration, which defines author and title
  metadata for the article. For example,

\begin{verbatim}
\begin{document}
\begin{frontmatter}
\title{Typesetting Guidelines for the\\ \textsl{Theory of Computing}}
\tocpdftitle{Typesetting Guidelines for the Theory of Computing}
\tocpdfauthor{First Author, Second Author, et. al.}

\author[first]{First Author\thanks{Supported by GGA Grant \# 142847.}}
\author{Second Author\thanks{Supported by XYZ Grant \# 271828.}}}
\author[third]{Third Author}

\begin{abstract}
   This article provides typesetting guidelines for the 
   \textsl{Theory of Computing} Journal.
\end{abstract}

\tockeywords{Guidelines, toc.cls, typesetting}
\tocams{Does not fall under AMS Classification}
\tocacm{Does not fall under ACM Classification}

\end{frontmatter}
...
\end{verbatim}
Inside the \verb'frontmatter' environment, use the \verb`\tocpdftitle`
and \verb`\tocpdfauthor` commands to setup the title and author
metadata information for the PDF file. \emph{Note that arguments to
these should not use LaTeX
constructs}.  The title, author(s), abstract, keywords and
other metadata associated with your article are assigned as above. One
\verb`\author` command should appear for  each author. Footnotes on 
author names may be obtained by the \verb'\thanks' command, as above. 

Refrain from using long footnotes inside \verb'\thanks'. Use the 
\texttt{tocauthors} and \texttt{tocaboutauthors} environments instead.
The optional argument below is used to associate the author's name with
the
author's institution, email addresses and other information. 
This additional information is provided using the \texttt{tocauthors} 
and \texttt{tocaboutauthors} environments as shown below. These 
environments should be placed after the bibliography.

\begin{verbatim}
...
\begin{document}
\begin{frontmatter}
  ...
\end{frontmatter}
% The article comes here
...
\bibliography{example}
\bibliographystyle{tocplain}

\begin{tocauthors}
\begin{tocinfo}[first]
   First Author \tocabout{}\\
   First Institution \\
   myemail\tocat{}mydept\tocdot{}myuniv\tocdot{}edu
\end{tocinfo}
\begin{tocinfo}[third]
   Third Author \\
   Third Institution \\
   anotheremail\tocat{}anotherdept\tocdot{}anotheruniv\tocdot{}edu
\end{tocinfo}
\end{tocauthors}

\begin{tocaboutauthors}
   \begin{tocabout}[first]
First Author, did his Ph.D. from University of \Pi. 
His advisor was \href{http://someplace.somewhere.net}{nobody}. 
He is interested in Communication Complexity and Game Theory.
His hobbies include Skiing and Fishing.
   \end{tocabout}
\end{tocaboutauthors}
\end{document}
\end{verbatim}

The \verb`\tocabout` macro in the \texttt{tocinfo} environment
creates a link to the ``About the Author'' information specified 
in the \verb`\tocaboutauthors` environment.

\section{General typesetting requests}

Use the \verb'\section' command to break your exposition into natural
sections. For example
\begin{verbatim}
\section{General typesetting requests}
\end{verbatim}
was the command used to typeset the beginning of this section.

\begin{sloppypar}
  Please use \verb'\emph' rather than \verb'\em' to \emph{emphasize}
  text, as \verb'\emph' is smart about space following the emphasized
  text. Similarly, use the \LaTeX2e commands \verb'\texttt',
  \verb'\textsl', \verb'\textit', \verb'\textsf', and \verb'\textbf',
  to produce \texttt{teletype}, \textsl{slanted}, \textit{italic},
  \textsf{sans-serif}, and \textbf{bold} text.  In math mode, please
  use the math mode commands \verb'\mathrm' and \verb'\mathbf'
  commands to produce $\mathrm{Roman}$ and $\mathbf{boldface}$
  characters.  $\mathcal{CALLIGRAPHIC}$ characters are produced by the
  \verb'\mathcal' command (in math mode only).  Use \verb'\N',
  \verb'\Z', \verb'\Q', \verb'\R', and \verb'\C' to produce the
  symbols for the five common number systems; they will be typeset in
  blackboard-bold as $\N$, $\Z$, $\Q$, $\R$, $\C$.  Use the
  \verb'\mathbb' command to create other blackboard-bold characters in
  math mode; for instance \verb'\mathbb{H}' will produce $\mathbb{H}$,
  the standard symbol for the quaternions.
\end{sloppypar}

\section{Figures and included images}

If you wish to include images in your article, please use the
\verb'\includegraphics' command in the \texttt{graphicx} package. Add
\begin{verbatim}
\usepackage{graphicx}
\end{verbatim}
in the preamble, after the \verb'\documentclass{toc}' command.
Usage of
\texttt{epic} and \texttt{eepic} are also encouraged, in general, for
generating figures. Included images should always appear within a
figure environment:
\begin{verbatim}
\begin{figure}
  \begin{center}
    \includegraphics[scale=0.6]{petersen}
  \end{center}
  \caption{Petersen's graph: an included image.}
\end{figure}
\end{verbatim}
\begin{figure}
  \begin{center}
    \includegraphics[scale=0.6]{petersen}  %   An included image.
  \end{center}
  \caption{Petersen's graph: an included image.}
\end{figure}
As \emph{Theory of Computing} publishes articles using Adobe's acrobat
format, we ask that you provide versions of your included figures in
this format. Figures in encapsulated postscript format can be used to
generate acrobat figures by the \texttt{epstopdf} program, also
available in the comprehensive \TeX\ archive network at
\begin{center}
  \url{http://www.ctan.org/tex-archive/support/epstopdf/}\enspace.
\end{center}

If you are having BoundingBox issues you may find the 
\texttt{epstool} program useful. This program can be found at
\begin{center}
\url{http://www.cs.wisc.edu/~ghost/gsview/epstool.htm}
\end{center}

\paragraph{Remark.} The \verb'\includegraphics' command adapts 
its behavior depending on whether your \LaTeX\ file is compiled 
with \texttt{latex} or \texttt{pdflatex}; so long as you do not 
have an extension on the filename in the \verb'\incudegraphics' 
command (as above), it will attempt to load the file with a 
\texttt{.pdf} extension when called from \texttt{pdflatex} and 
a \texttt{.eps} extension when called from \texttt{latex}.

\section{Mathematical formul\ae{} and proofs}

The AMS theorem class is loaded by default, which means that theorems,
definitions, etc. are coded as follows:

\begin{theorem}[Markov's inequality]
  Let $X$ be a positive real-valued random variable.  Then, for
  every positive $\alpha$,
\begin{equation} \label{markov.eq}
  \Pr [ X \geq \alpha ] \leq \frac{E[X]}{\alpha}\enspace.
\end{equation}
\end{theorem}

Constructs for propositions, corollaries, claims, and lemmas are
predefined, invoked as above, and share numbering with theorems. For 
example:

\begin{proposition}[Chebyshev's inequality]\label{prop:Chebyshev}
  Let $X$ be a real-valued random variable.  Then, for every positive
  $\lambda$,
  $$
  \Pr \bigl[ | X - E[X]| \geq \lambda \bigr] \leq 
\frac{\sigma^2[X]}{\lambda^2}\enspace.
  $$
\end{proposition}
\begin{sloppypar}
  Similar environments for definitions, conjectures, examples,
  remarks, and facts are also defined. They are typeset slightly
  differently but do share numbering with the constructs above. For
  example
\begin{definition}\label{def:stddev}
  Let $X$ be a real-valued random variable for which $E[X^2] <
  \infty$. The \emph{standard deviation} of $X$, denoted 
  $\sigma[X]$, is given by
  $$
  \sigma[X] = \sqrt{E\left[\bigl(X - E[X]\bigr)^2\right]}\enspace.
  $$
\end{definition}
If you wish to define a new theorem-like environment (\texttt{idea},
for example), you must inform \LaTeX\ about the environment in the
preamble of your document (that is, between the
\verb'\documentclass{toc}' command and the \verb'\begin{document}' 
command). If
  you wish to define the environment so that it is typeset like a
  Theorem (text in Italics), use the sequence of commands:
\end{sloppypar}
\begin{verbatim}
\theoremstyle{plain}
\newtheorem{idea}[theorem]{Idea}
\end{verbatim}
If you wish to define an environment so that it is typeset like a
Definition (text in Roman), use the sequence of commands:
\begin{verbatim}
\theoremstyle{definition}
\newtheorem{thought}[theorem]{Thought}
\end{verbatim}
Proceed to use the construct in the body of your article as follows:
\begin{verbatim}
\begin{idea}
  Use binary-coded-decimal instead of the long code.
\end{idea}
\end{verbatim}
  This will produce the output:
\begin{idea}
  Use binary-coded-decimal instead of the long code.
\end{idea}
With the \texttt{thought} environment, the code will be this:
\begin{verbatim}
\begin{thought}
  Use binary-coded-decimal instead of the long code.
\end{thought}
\end{verbatim}
  This will produce the output:
\begin{thought}
  Use binary-coded-decimal instead of the long code.
\end{thought}

Proofs simply use the \texttt{proof} environment:

\begin{proof}[Proof of Markov's inequality.]
  To prove inequality~\eqref{markov.eq}, expand the definition of
$E[X]$.
\end{proof}

\paragraph{Equations.} Unnumbered equations,
like the one appearing in \propref{prop:Chebyshev} above, are
produced by the \verb'$$' (or \verb'\[' and \verb'\]') delimiters: for
example,
\begin{verbatim}
$$
\sigma^2[X] = E\Bigl[\bigl(X - E[X]\bigr)\Bigr]\enspace.
$$
\end{verbatim}
produces the equation
$$
\sigma^2[X] = E\Bigl[\bigl(X - E[X]\bigr)^2\Bigr]\enspace.
$$
Please use \verb'\enspace', as above, to provide enough space between
equations and any following punctuation. Note how the size of
delimiters such as $|$ and $[$ can be changed in an equation by use of
the modifiers \verb'\bigl' and \verb'\Bigl'. To have \LaTeX\
automatically adjust the size of such delimiters, use \verb'\left' and
\verb'\right', as in Equation~\eqref{eq:covariance} below.

Numbered equation are produced using the standard equation
environment. For example, the \LaTeX\ code
\begin{verbatim}
\begin{equation}
  \label{eq:covariance}
  \cov[X,Y] = E\left[\bigl(X - E[X]\bigr)
    \bigl(Y - E[Y]\bigr)\right]\enspace.
\end{equation}
\end{verbatim}
produces the equation
\begin{equation}
  \label{eq:covariance}
  \cov[X,Y] = 
       E\left[\bigl(X - E[X]\bigr)\bigl(Y - E[Y])\right]\enspace.
\end{equation}
Observe that equations numbers have the form $(s.n)$, where $s$ is a
section number and $n$ is a subordinate equation number. To refer to
an equation from the main text body, use the \verb'\eqref' command
with the label attached to the equation by the \verb'\label'
command. For example, the reference Equation~\eqref{eq:covariance} is
produced by the \LaTeX\ code
\verb'Equation~\eqref{eq:example}'.

\section{Labels and References}
Labels are attached to theorems and such using the command 
\verb`\label{labelname}` and usually referred to by using 
\verb`\ref{labelname}`. Though not required by \LaTeX\ it is 
advisable that the label names, follow a prefix convention
that can used to identify the type of label. For example, 
labels attaches to Theorems should be prefixed by \texttt{thm:}.
This makes copy editing the \LaTeX\ file easier.

In order to simplify phrases like
\verb`Lemma~\ref{lem:labelname}`, toc.cls provides a number of 
\verb`\ref`-like environments. For example, to refer to the 
lemma labelled \texttt{lem:labelname}, you can use 
\verb`\lemref{lem:labelname}`. This will generate the word 
\texttt{Lemma} as well as make it easier for the reader to 
navigate through your document (clicking on Lemma will take the
reader to the referred lemma). The predefined list of 
\verb`\ref`-variants include\footnote{See source file for other
variants}:

\bigskip

\begin{tabular}{rl|rl}
\texttt{lemref} & (Lemma) & \texttt{thmref} & (Theorem) \\
\texttt{propref} & (Proposition)  & \texttt{corref}  & (Corrolary) \\
\texttt{secref} & (Section)   & \texttt{subsecref} & (Subsection) \\
\texttt{exerref} & (Exercise) & \texttt{factref} & (Fact) \\
\texttt{defnref} & (Definition) & \texttt{egref} & (Example) \\
\texttt{remref} & (Remark)
\end{tabular}

\section{Bibliography}

All the Bibliography entries should be formatted according to 
toc guidelines. These guidelines are implemented via the BibTeX 
style file \texttt{tocplain.bst}, which can be downloaded from 
the journal website. Hence authors are encouraged to use BibTeX 
databases for the bibliographies as opposed to using the 
\texttt{thebibliography} environment directly in the LaTeX 
source. Authors are also encouraged to use the "url,ps,pdf" 
fields in the BibTeX entry to indicate an internet URL where 
the full text of the cited material is available. Preference 
should be given to URLs without access restrictions. When 
specifying a URL ensure that it starts with \texttt{http://}.

\bibliography{example}
\bibliographystyle{tocplain}
\nocite{*}

\begin{tocauthors}
\begin{tocinfo}[alex]
  Alexander Russell \tocabout \\
  associate professor \\
  University of Connecticut, Storrs, CT\\
  acr\tocat{}cse\tocdot{}uconn\tocdot{}edu \\
  \url{http://www.engr.uconn.edu/~acr}
\end{tocinfo}
\begin{tocinfo}[john]
  John C. Milestone \tocabout\\
  lecturer \\
  University of Chicago, Chicago, IL\\
  milestone\tocat{}cs\tocdot{}uchicago\tocdot{}edu \\
  \url{http://people.cs.uchicago.edu/~milestone}
\end{tocinfo}
\begin{tocinfo}
  K\'alm\'an Sz\H{o}l\H{o}ssy\\
  senior research associate \\
  TOC Hungary Inc., Kecskem\'et, Hungary\\
  kszolos\tocat{}ailab\tocdot{}toc\tocdot{}hu \\
  \url{http://www.toc.hu/~kalman}
\end{tocinfo}
\begin{tocinfo}
  L\'aszl\'o Sz\H{o}l\H{o}ssy\\
  junior research associate\footnote{
    At the time of submission, this author was
    a graduate student at the University of
    Connecticut, Storrs, CT.} \\
  TOC Hungary Inc., Kecskem\'et, Hungary\\
  lszolos\tocat{}ailab\tocdot{}toc\tocdot{}hu \\
  \url{http://www.toc.hu/~laci}
\end{tocinfo}
\begin{tocinfo}
  M\'aria Sz\H{o}l\H{o}ssy\\
  graduate student \\
  University of Connecticut, Storrs, CT\\
  mszolos\tocat{}cse\tocdot{}uconn\tocdot{}edu \\
  \url{http://www.engr.uconn.edu/~mariads}
\end{tocinfo}
\begin{tocinfo}
  N\'andor Sz\H{o}l\H{o}ssy\\
  toddler\footnote{Infant at the time of submission.}  \\
  Storrs South Day Care, Storrs, CT\\
  mszolos\tocat{}cse\tocdot{}uconn\tocdot{}edu \\
  \url{http://www.toc.hu/~laci}
\end{tocinfo}
\begin{tocinfo}
  Orb\'an Sz\H{o}l\H{o}ssy\\
  consultant \\
  Orban Consulting\\
  Palo Alto, CA \\
  orban\tocat{}orban\tocdot{}com \\
  \url{http://orban.com}
\end{tocinfo}
\end{tocauthors}

\begin{tocaboutauthors}
\begin{tocabout}[alex]
{\sc Alex Russell} graduated from M.I.T.  in 1996.  His advisor
was Mike Sipser.  His CS interests include distributed computing,
quantum computation, interactive proofs, cryptography, information
theory, and group theory.  He also enjoys cycling,
raising his two kids, and editing the \textsf{Theory of Computing}.
\end{tocabout}
\begin{tocabout}[john]
{\sc John C. Milestone} has Masters Degree in accounting from Wabash
College, Granville, IL and is currently considering graduate study
in computer science.  He also enjoys watching the Chicago
skyline.\footnote{This footnote to test width problems which might
happen}
\end{tocabout}
\begin{tocabout}
No information is available about the {\sc Sz\H{o}l\H{o}ssy}s except
that Orb\'an was born in Buenos Aires and is no relation to his
namesakes.
\end{tocabout}
\end{tocaboutauthors}

\end{document}

