\def\draft{0}
\ifnum\draft=1
\newcommand{\Snote}[1]{\textbf{[Salil's Note: #1]}}
\else
\newcommand{\Snote}[1]{}
\fi

\newtheorem{theorem}{Theorem}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{openprob}[theorem]{Open Problem}
\newtheorem{remk}[theorem]{Remark}
\newtheorem{exmp}[theorem]{Example}
\newtheorem{apdxlemma}{Lemma}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{exercises}[theorem]{Exercises}

\newenvironment{example}{\begin{exmp}
\begin{normalfont}}{\end{normalfont}
\end{exmp}}

\newenvironment{remark}{\begin{remk}
\begin{normalfont}}{\end{normalfont}
\end{remk}}
\newtheorem{sublemma}[theorem]{Sublemma}


%%%%%%%%%%%%%%%%%%%% proof environments

\def\FullBox{\hbox{\vrule width 8pt height 8pt depth 0pt}}

\def\qed{\ifmmode\qquad\FullBox\else{\unskip\nobreak\hfil
\penalty50\hskip1em\null\nobreak\hfil\FullBox
\parfillskip=0pt\finalhyphendemerits=0\endgraf}\fi}

\def\qedsketch{\ifmmode\Box\else{\unskip\nobreak\hfil
\penalty50\hskip1em\null\nobreak\hfil$\Box$
\parfillskip=0pt\finalhyphendemerits=0\endgraf}\fi}

\newenvironment{proof}{\begin{trivlist} \item {\bf Proof:~~}}
  {\qed\end{trivlist}}

\newenvironment{proofsketch}{\begin{trivlist} \item {\bf
Proof Sketch:~~}}
  {\qedsketch\end{trivlist}}

\newenvironment{proofof}[1]{\begin{trivlist} \item {\bf Proof
#1:~~}}
  {\qed\end{trivlist}}

\newenvironment{claimproof}{\begin{quotation} \noindent
{\bf Proof of claim:~~}}{\qedsketch\end{quotation}}


%%%%%%%%%%%%%%%%%%%%%%% text macros
\newcommand{\etal}{{\it et~al.\ }}
\newcommand{\ie} {{\it i.e.,\ }}
\newcommand{\eg} {{\it e.g.,\ }}
\newcommand{\cf}{{\it cf.,\ }}

%%%%%%%%%%%%%%%%%%%%%%% general useful macros
\newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\N}{{\mathbb{N}}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\F}{{\mathbb F}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\poly}{{\mathrm{poly}}}
\newcommand{\polylog}{{\mathrm{polylog}}}
\newcommand{\loglog}{{\mathop{\mathrm{loglog}}}}
\newcommand{\zo}{\{0,1\}}
\newcommand{\suchthat}{{\;\; : \;\;}}
\newcommand{\pr}[2][]{\Pr_{#1}\left[#2\right]}
% \newcommand{\pr}[1]{\Pr\left[#1\right]}
\newcommand{\deffont}{\em}
\newcommand{\getsr}{\mathbin{\stackrel{\mbox{\tiny R}}{\gets}}}
\newcommand{\Exp}{\mathop{\mathrm E}\displaylimits}
\newcommand{\Var}{\mathop{\mathrm Var}\displaylimits}
\newcommand{\xor}{\oplus}


%%%%%%%%%%%%%%%%%%% macros particular to this course
\def\textprob#1{\textmd{\textsc{#1}}}
\newcommand{\mathprob}[1]{\mbox{\textmd{\textsc{#1}}}}
\newcommand{\SAT}{\mathprob{SAT}}
\newcommand{\QuadRes}{\textprob{Quadratic Residuosity}}
\newcommand{\CktApprox}{\mathprob{Circuit-Approx}}
\newcommand{\CktRelApprox}{\mathprob{Circuit-RelApprox}}
\newcommand{\DNFRelApprox}{\mathprob{DNF-RelApprox}}
\newcommand{\GraphNoniso}{\textprob{Graph Nonisomorphism}}
\newcommand{\GNI}{\mathprob{GNI}}
\newcommand{\GraphIso}{\textprob{Graph Isomorphism}}
\newcommand{\GI}{\mathprob{GI}}
\newcommand{\MinCut}{\textprob{Min-Cut}}
\newcommand{\MaxCut}{\textprob{Max-Cut}}
\newcommand{\MaxFlow}{\textprob{Max Flow}}
\newcommand{\IdentityTest}{\textprob{Identity Testing}}
\newcommand{\GraphConn}{\textprob{Graph Connectivity}}
\newcommand{\Primality}{\textprob{Primality}}
\newcommand{\USTConn}{\textprob{Undirected S-T Connectivity}}
\newcommand{\PerfMatch}{\textprob{Perfect Matching}}

\newcommand{\yes}{{\sc yes}}
\newcommand{\no}{{\sc no}}

\newcommand{\class}[1]{\mathbf{#1}}
\newcommand{\coclass}[1]{\mathbf{co\mbox{-}#1}} % and their complements
\newcommand{\BPP}{\class{BPP}}
\newcommand{\NP}{\class{NP}}
\newcommand{\coNP}{\coclass{NP}}
\newcommand{\RP}{\class{RP}}
\newcommand{\coRP}{\coclass{RP}}
\newcommand{\ZPP}{\class{ZPP}}
\newcommand{\RNC}{\class{RNC}}
\newcommand{\RL}{\class{RL}}
\renewcommand{\L}{\class{L}}
\newcommand{\coRL}{\coclass{RL}}
\newcommand{\IP}{\class{IP}}
\newcommand{\AM}{\class{AM}}
\newcommand{\MA}{\class{MA}}
\renewcommand{\P}{\class{P}}
\newcommand\prBPP{\class{prBPP}}
\newcommand\prRP{\class{prRP}}
\newcommand\prP{\class{prP}}
\newcommand{\Ppoly}{\class{P/poly}}
\newcommand{\DTIME}{\class{DTIME}}
\newcommand{\ETIME}{\class{E}}
\newcommand{\BPTIME}{\class{BPTIME}}
\newcommand{\EXP}{\class{EXP}}
\newcommand{\SUBEXP}{\class{SUBEXP}}
\newcommand{\qP}{\class{\tilde{P}}}
\newcommand{\PH}{\class{PH}}
\newcommand{\NC}{\class{NC}}
\newcommand{\PSPACE}{\class{PSPACE}}
\newcommand{\quasiP}{\class{\tilde{P}}}
\newcommand{\BPAC}{\class{BPAC_0}}
\newcommand{\qAC}{\class{\widetilde{AC}_0}}

\newcommand{\negl}{{\mathrm{neg}}}
\newcommand{\Diam}{\mathrm{Diam}}
\newcommand{\Cut}{\mathrm{Cut}}
\newcommand{\pf}{\mathit{pf}}
\newcommand{\Col}{\mathrm{Col}}
\newcommand{\Supp}{\mathrm{Supp}}

\newcommand{\accept}{\mathtt{accept}}
\newcommand{\reject}{\mathtt{reject}}
\newcommand{\fail}{\mathtt{fail}}
\newcommand{\halt}{\mathtt{halt}}


\newcommand{\HFam}{\mathcal{H}}
\newcommand{\FFam}{\mathcal{F}}
\newcommand{\Dom}{\mathcal{D}}
\newcommand{\Rng}{\mathcal{R}}

\newcommand{\Hall}{\mathrm{H}}
\newcommand{\Hmin}{\mathrm{H}_{\infty}}
\newcommand{\HRen}{\mathrm{H}_2}
\newcommand{\HSha}{\mathrm{H}_{\mathit{Sh}}}
\newcommand{\Ext}{\mathrm{Ext}}
\newcommand{\Con}{\mathrm{Con}}
\newcommand{\Samp}{\mathrm{Smp}}
\newcommand{\Enc}{\mathrm{Enc}}
\newcommand{\Code}{\mathcal{C}}

\newcommand{\zigzag}{\mathbin{\raisebox{.2ex}{
      \hspace{-.4em}$\bigcirc$\hspace{-.75em}{\rm
      z}\hspace{.15em}}}}

\newcommand{\eps}{\varepsilon}
\newcommand{\ci} {\stackrel{\rm{c}}{\equiv}}
\newcommand{\Time}{\mathrm{time}}
\newcommand{\Adv}{\mathrm{adv}}
\newcommand{\inner}[2]{\left[#1,#2\right]}

\newcommand{\GL}{\operatorname{GL}}
\newcommand{\maj}{\operatornamewithlimits{maj}}



% Copied from macros in the textbook version
\newcommand{\Sampling}{\textprob{Sampling}}
\newcommand{\replacement}{\mathbin{\raisebox{.2ex}{
      \hspace{-.4em}$\bigcirc$\hspace{-.75em}{\rm
      r}\hspace{.15em}}}}
\newcommand{\hatn}{{\hat{n}}}

\newcommand{\Dec}{\mathrm{Dec}}
\newcommand{\Class}{\mathcal{C}}

\newcommand{\Disp}{\mathrm{Disp}}
\newcommand{\LIST}{\mathrm{LIST}}


\newcommand{\GF}{\mathrm{GF}}
\newcommand{\Cay}{\mathrm{Cay}}
\newcommand{\davg}{d_{\mathit{avg}}}
\newcommand{\dmax}{d_{\mathit{max}}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\del}{\partial}
\newcommand{\pimin}{\pi_{\mathit{min}}}
\newcommand{\Dout}{D_{\mathit{out}}}
\newcommand{\diag}{\mathrm{diag}}
\newcommand{\tomega}{\tilde{\omega}}
\newcommand{\Wreg}{W_\mathit{reg}}
\newcommand{\omegareg}{\omega_{\mathit{reg}}}
\newcommand{\tomegareg}{\tilde{\omega}_{\mathit{reg}}}
\newcommand{\dout}{d_{\mathit{out}}}
\newcommand{\dmin}{d_{\mathit{min}}}
\newcommand{\wmin}{w_{\mathit{min}}}
\newcommand{\wmax}{w_{\mathit{max}}}

\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\renewcommand{\Exp}{\mathop{\mathbb{E}}}

\newcommand{\Greg}{G_{\mathit{reg}}}
\newcommand{\Nreg}{N_{\mathit{reg}}}