\newtheorem{theorem}{Theorem}
\newtheorem{conjecture}[theorem]{Conjecture}
\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{apdxlemma}{Lemma}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{problem}{Problem}

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



%%%%%%%%%%%%%%%%%%%%%%% 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{\poly}{{\mathrm{poly}}}
\newcommand{\polylog}{{\mathrm{polylog}}}
\newcommand{\loglog}{{\mathop{\mathrm{loglog}}}}
\newcommand{\zo}{\{0,1\}}
\newcommand{\bits}{\{-1, 1\}}
\newcommand{\suchthat}{{\;\; : \;\;}}
\newcommand{\pr}[1]{\Pr\left[#1\right]}
\newcommand{\deffont}{\em}
\newcommand{\getsr}{\mathbin{\stackrel{\mbox{\tiny R}}{\gets}}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Ex}[2]{\mathop{\mathbb{E}}_{#1}\left[#2\right]}
\newcommand{\Var}[2]{\mathop{\mathrm{Var}}_{#1}\left[#2\right]}
\newcommand{\eps}{\varepsilon}
\newcommand{\one}{\mathbf{1}}

%%%%%%%%%%%%%%%%%%%%%%%%%% linear algebra
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\sgnrank}{\operatorname{rank}_{\pm}}
\newcommand{\spn}{\operatorname{span}}
\newcommand{\arank}{\operatorname{arank}}


%%%%%%%%%%%%%%%%%%% macros particular to this course

\def\textprob#1{\textmd{\textsc{#1}}}
\newcommand{\mathprob}[1]{\mbox{\textmd{\textsc{#1}}}}
\newcommand{\SAT}{\mathprob{SAT}}
\newcommand{\yes}{{\sc yes}}
\newcommand{\no}{{\sc no}}

\newcommand{\class}[1]{\mathbf{#1}}
\newcommand{\SZK}{\class{SZK}}
\newcommand{\BPP}{\class{BPP}}
\newcommand{\NP}{\class{NP}}
\renewcommand{\P}{\class{P}}
\newcommand{\RP}{\class{RP}}
\newcommand{\PSPACE}{\class{PSPACE}}
\newcommand{\MA}{\class{MA}}
\newcommand{\negl}{{\mathrm{neg}}}


\newcommand{\Ccc}{\class{\mathcal{C}^{cc}}}
\newcommand{\Pcc}{\class{P^{cc}}}
\newcommand{\PPcc}{\class{PP^{cc}}}
\newcommand{\UPPcc}{\class{UPP^{cc}}}
\newcommand{\BPPcc}{\class{BPP^{cc}}}
\newcommand{\BPPpriv}[1]{\class{BPP}^{priv}_{#1}}
\newcommand{\BPPpub}[1]{\class{BPP}^{pub}_{#1}}
\newcommand{\NPcc}{\class{NP^{cc}}}
\newcommand{\coNPcc}{\class{coNP^{cc}}}
\newcommand{\Sigmacc}[1]{\class{\Sigma^{cc}_{#1}}}
\newcommand{\MAcc}{\class{MA^{cc}}}
\newcommand{\RPcc}{\class{RP^{cc}}}
\newcommand{\coRPcc}{\class{coRP^{cc}}}
\newcommand{\ZPPcc}{\class{ZPP^{cc}}}

\newcommand{\Cdt}{\class{\mathcal{C}^{dt}}}
\newcommand{\Pdt}{\class{P^{dt}}}
\newcommand{\PPdt}{\class{PP^{dt}}}
\newcommand{\UPPdt}{\class{UPP^{dt}}}
\newcommand{\BPPdt}{\class{BPP^{dt}}}
\newcommand{\NPdt}{\class{NP^{dt}}}
\newcommand{\coNPdt}{\class{coNP^{dt}}}
\newcommand{\Sigmadt}[1]{\class{\Sigma^{dt}_{#1}}}
\newcommand{\MAdt}{\class{MA^{dt}}}
\newcommand{\RPdt}{\class{RP^{dt}}}
\newcommand{\coRPdt}{\class{coRP^{dt}}}
\newcommand{\ZPPdt}{\class{ZPP^{dt}}}

\newcommand{\ICext}[1]{IC^{\mathrm{ext}}_{#1}}
\newcommand{\IC}[1]{IC_{#1}}
\newcommand{\CC}[1]{CC_{#1}}

\newcommand{\sgn}{\operatorname{sgn}}

%%%%%%Gates%%%%%%%%
\newcommand{\THR}{\mathrm{THR}}
\newcommand{\MAJ}{\mathrm{MAJ}}
\newcommand{\AND}{\mathrm{AND}}
\newcommand{\OR}{\mathrm{OR}}
\newcommand{\XOR}{\mathrm{XOR}}

%%%%%%%Functions%%%%%
\newcommand{\EQ}{\mathrm{EQ}}
\newcommand{\GT}{\mathrm{GT}}
\newcommand{\DISJ}{\mathrm{DISJ}}
\newcommand{\UDISJ}{\mathrm{UDISJ}}
\newcommand{\IP}{\mathrm{IP}}
\newcommand{\INT}{\mathrm{INT}}
\newcommand{\IND}{\mathrm{IND}}
\newcommand{\AIND}{\mathrm{AIND}}
\newcommand{\GH}{\mathrm{GH}}
\newcommand{\STCONN}{\mathrm{STCONN}}

\newcommand{\cost}{\operatorname{cost}}
\newcommand{\lecc}{\le_{cc}}
\newcommand{\val}{\mathrm{val}}
\newcommand{\disc}{\mathrm{disc}}
\newcommand{\KW}{\mathrm{KW}}
\newcommand{\PM}{\operatorname{PM}}

\newcommand{\DT}{\operatorname{DT}}
\newcommand{\C}{\operatorname{CC}}
\newcommand{\Inf}{\mathbf{\mathop{Inf}}}
\newcommand{\I}{\mathbf{I}}
\newcommand{\MaxInf}{\mathbf{MaxInf}}
\newcommand{\Stab}{\mathbf{\mathop{Stab}}}
\newcommand{\NS}{\mathbf{\mathop{NS}}}
\newcommand{\W}{\mathbf{\mathop{W}}}
\newcommand{\dist}{\operatorname{dist}}

\newcommand{\Sim}{\mathrm{Sim}}
\newcommand{\avg}{\mathrm{avg}}
\newcommand{\dens}{\mathrm{dens}}

\newcommand{\adeg}{\operatorname{adeg}}

\newcommand{\Pat}{\operatorname{PM}}

