\documentclass[11pt]{article} \usepackage{complexity} \Homework{0} \Name{Eric Blais} \Collaboration{I discussed the outline for this document with Ryan O'Donnell and Venkatesan Guruswami. Ryan also provided most of the commands defined in the style file. (In your homeworks, please explain how you collaborated with other students; don't just list the names of people with whom you collaborated.)} \begin{document} \MakeHeader \section{Problem 1} Please remember to write solutions that are clear and concise. Two resources that may be particularly helpful for writing homework solutions are the first chapter of {\it Mathematical Writing}~\cite{KLR96} and {\it The Not So Short Introduction to \LaTeXe}~\cite{OPHS08}. The former contains a list of simple guidelines for writing mathematics clearly; the latter is a good reference for \LaTeX. \section{Problem 2} In the \texttt{complexity.sty} file, we have defined some commands that you may find useful in your solutions. It includes commands for quickly writing the names of some complexity classes such as \P, \NP, and \EXP. It also includes shortcuts for writing mathematical statements, as the following Proposition illustrates. \begin{proposition} For any function $f : \bitsn \to \R$, if there is a set $\calA \subseteq \bitsn$ such that $$ \Ex_{\bx \in \calA}[ f(x) ] \ge \eps, $$ then there exists an element $x \in \calA$ such that $f(x) \ge \eps$. \end{proposition} (See the \LaTeX\ source of this document to view how the shortcut commands are used.) \bibliography{sample} \end{document}