\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}}}