\usepackage{amsmath,amssymb,amsthm,amsfonts,latexsym,bbm,xspace,graphicx,float,mathtools}
\usepackage[backref,colorlinks,citecolor=blue,bookmarks=true]{hyperref}
\usepackage[letterpaper,margin=1in]{geometry}
\usepackage{enumitem}
\usepackage[protrusion=true,expansion=true]{microtype}

\usepackage[T1]{fontenc}
\usepackage{fouriernc}
\usepackage[mathscr]{euscript}

\usepackage[colorinlistoftodos]{todonotes}
\usepackage{combelow} %for you, Rusins Freivalds


% environments
\newtheorem{theorem}{Theorem}[section]
\newtheorem*{namedtheorem}{\theoremname}
\newcommand{\theoremname}{testing}
\newenvironment{named}[1]{ \renewcommand{\theoremname}{#1} \begin{namedtheorem}} {\end{namedtheorem}}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{corollary}[theorem]{Corollary}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{example}[theorem]{Example}
\newtheorem{examples}[theorem]{Examples}



%%%%%%%%%%%% Generic math macros %%%%%%%%%%%%

% probability and other mathops
\renewcommand{\Pr}{\mathop{\bf Pr\/}} 
\newcommand{\E}{\mathop{\bf E\/}}
\newcommand{\Ex}{\mathop{\bf E\/}}
\newcommand{\Es}[1]{\mathop{\bf E\/}_{{\substack{#1}}}}           
\newcommand{\Var}{\mathop{\bf Var\/}}
\newcommand{\Cov}{\mathop{\bf Cov\/}}
\newcommand{\stddev}{\mathop{\bf stddev\/}}
\newcommand{\littlesum}{\mathop{{\textstyle \sum}}}
\newcommand{\littleprod}{\mathop{{\textstyle \prod}}}
\newcommand{\apx}{\mathop{\approx}}


% mathrm terms         
\newcommand{\tr}{\mathrm{tr}} \newcommand{\Tr}{\tr}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\polylog}{\mathrm{polylog}}
\newcommand{\size}{\mathrm{size}}
\newcommand{\avg}{\mathop{\mathrm{avg}}}
\newcommand{\odd}{\mathrm{odd}}
\newcommand{\even}{\mathrm{even}}
\newcommand{\sgn}{\mathrm{sgn}}
\newcommand{\dist}{\mathrm{dist}}
\newcommand{\hamdist}{\mathrm{Dist}}
\newcommand{\step}{\mathrm{step}}
\newcommand{\sens}{\mathrm{sens}}
\newcommand{\spn}{\mathrm{span}}
\newcommand{\supp}{\mathrm{supp}}
\newcommand{\Aut}{\mathrm{Aut}}
\newcommand{\CSP}{\mathrm{CSP}}
\newcommand{\Val}{\mathrm{Val}}
\newcommand{\Opt}{\mathrm{Opt}}
\newcommand{\SDPVal}{\mathrm{SDPVal}}
\newcommand{\SDPOpt}{\mathrm{SDPOpt}}

\newcommand{\codim}{\operatorname{codim}}

\newcommand{\AND}{\mathrm{AND}}
\newcommand{\OR}{\mathrm{OR}}
\newcommand{\tribes}{\mathrm{Tribes}}   \newcommand{\Tribes}{\tribes}
\newcommand{\maj}{\mathrm{Maj}}         \newcommand{\Maj}{\maj}
\newcommand{\equ}{\mathrm{Equ}}         \newcommand{\EQU}{\equ}
\newcommand{\two}{\mathrm{Two}}         \newcommand{\TWO}{\two}
\newcommand{\nae}{\mathrm{NAE}}         \newcommand{\NAE}{\nae}
\newcommand{\sort}{\mathrm{Sort}}       \newcommand{\Sort}{\mathrm{Sort}}       \newcommand{\SORT}{\sort}
\newcommand{\oxr}{\mathrm{OXR}}         \newcommand{\OXR}{\oxr}
\newcommand{\sel}{\mathrm{Sel}}         \newcommand{\SEL}{\sel}
\newcommand{\IP}{\mathrm{IP}}
\newcommand{\CQ}{\mathrm{CQ}}

% number systems
\newcommand{\R}{\mathbbm R}
\newcommand{\C}{\mathbbm C}
\newcommand{\N}{\mathbbm N}
\newcommand{\Z}{\mathbbm Z}
\newcommand{\F}{\mathbbm F}
\newcommand{\Q}{\mathbbm Q}

% complexity classes
\newcommand{\PTIME}{\mathsf{P}}
\newcommand{\NP}{\mathsf{NP}} \newcommand{\np}{\NP}
\newcommand{\TC}{\mathsf{TC}}
\newcommand{\AC}{\mathsf{AC}}

% short forms
\newcommand{\eps}{\epsilon}
\newcommand{\lam}{\lambda}
\newcommand{\dleta}{\delta}
\newcommand{\vphi}{\varphi}
\newcommand{\bdry}{\partial}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\lv}{\lvert}
\newcommand{\rv}{\rvert}
\newcommand{\lV}{\lVert}
\newcommand{\rV}{\rVert}
\newcommand{\wt}[1]{\widetilde{#1}}
\newcommand{\wh}[1]{\widehat{#1}}
\newcommand{\ul}[1]{\underline{#1}}
\newcommand{\ol}[1]{\overline{#1}}
\newcommand{\ot}{\otimes}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\zo}{\{0,1\}}
\newcommand{\co}{:}                       %\newcommand{\co}{\colon}
\newcommand{\half}{\tfrac{1}{2}}
\newcommand{\bits}{\{-1,1\}}
\newcommand{\tf}{\{\true, \false\}}

% calligraphic letters
\newcommand{\calA}{\mathcal{A}}
\newcommand{\calB}{\mathcal{B}}
\newcommand{\calC}{\mathcal{C}}
\newcommand{\calE}{\mathcal{E}}
\newcommand{\calF}{\mathcal{F}}
\newcommand{\calG}{\mathcal{G}}
\newcommand{\calI}{\mathcal{I}}
\newcommand{\calJ}{\mathcal{J}}
\newcommand{\calO}{\mathcal{O}}
\newcommand{\calP}{\mathcal{P}}
\newcommand{\calQ}{\mathcal{Q}}
\newcommand{\calR}{\mathcal{R}}
\newcommand{\calS}{\mathcal{S}}
\newcommand{\calT}{\mathcal{T}}
\newcommand{\calU}{\mathcal{U}}
\newcommand{\calX}{\mathcal{X}}
\newcommand{\calY}{\mathcal{Y}}
\newcommand{\calZ}{\mathcal{Z}}

% bold
\newcommand{\bone}{\boldsymbol{1}}
\newcommand{\balpha}{\boldsymbol{\alpha}}
\newcommand{\bbeta}{\boldsymbol{\beta}}
\newcommand{\bgamma}{\boldsymbol{\gamma}}
\newcommand{\bomega}{\boldsymbol{\omega}}
\newcommand{\bpi}{\boldsymbol{\pi}}
\newcommand{\bphi}{\boldsymbol{\phi}}
\newcommand{\bvphi}{\boldsymbol{\varphi}}
\newcommand{\bpsi}{\boldsymbol{\psi}}
\newcommand{\bsigma}{\boldsymbol{\sigma}}
\newcommand{\btheta}{\boldsymbol{\theta}}
\newcommand{\bxi}{\boldsymbol{\xi}}
\newcommand{\ba}{\boldsymbol{a}}
\newcommand{\bb}{\boldsymbol{b}}
\newcommand{\bc}{\boldsymbol{c}}
\newcommand{\boldf}{\boldsymbol{f}}
\newcommand{\bg}{\boldsymbol{g}}
\newcommand{\bh}{\boldsymbol{h}}
\newcommand{\bi}{\boldsymbol{i}}
\newcommand{\bj}{\boldsymbol{j}}
\newcommand{\br}{\boldsymbol{r}}
\newcommand{\bs}{\boldsymbol{s}}
\newcommand{\bt}{\boldsymbol{t}}
\newcommand{\bu}{\boldsymbol{u}}
\newcommand{\bv}{\boldsymbol{v}}
\newcommand{\bw}{\boldsymbol{w}}
\newcommand{\bx}{{\boldsymbol{x}}}
\newcommand{\by}{\boldsymbol{y}}
\newcommand{\bz}{\boldsymbol{z}}
\newcommand{\bA}{\boldsymbol{A}}
\newcommand{\bB}{\boldsymbol{B}}
\newcommand{\bC}{\boldsymbol{C}}
\newcommand{\bD}{\boldsymbol{D}}
\newcommand{\bE}{\boldsymbol{E}}
\newcommand{\bF}{\boldsymbol{F}}
\newcommand{\bG}{\boldsymbol{G}}
\newcommand{\bH}{\boldsymbol{H}}
\newcommand{\bI}{\boldsymbol{I}}
\newcommand{\bJ}{\boldsymbol{J}}
\newcommand{\bL}{\boldsymbol{L}}
\newcommand{\bP}{\boldsymbol{P}}
\newcommand{\bR}{\boldsymbol{R}}
\newcommand{\bS}{\boldsymbol{S}}
\newcommand{\bT}{\boldsymbol{T}}
\newcommand{\bU}{\boldsymbol{U}}
\newcommand{\bV}{\boldsymbol{V}}
\newcommand{\bX}{\boldsymbol{X}}
\newcommand{\bY}{\boldsymbol{Y}}
\newcommand{\bZ}{\boldsymbol{Z}}

% bold calligraphic
\newcommand{\bcalG}{\boldsymbol{\calG}} \newcommand{\calbG}{\bcalG}
\newcommand{\bcalX}{\boldsymbol{\calX}} \newcommand{\calbX}{\bcalX}
\newcommand{\bcalY}{\boldsymbol{\calY}} \newcommand{\calbY}{\bcalY}
\newcommand{\bcalZ}{\boldsymbol{\calZ}} \newcommand{\calbZ}{\bcalZ}

% barred letters
\newcommand{\barJ}{{\overline{J}}}
\newcommand{\barT}{{\overline{T}}}

% more symbols
\newcommand{\indic}[1]{1_{#1}}   
\newcommand{\simplex}{\triangle}
\newcommand{\grad}{\nabla}
\newcommand{\symmdiff}{\triangle} \newcommand{\symdiff}{\symmdiff}
\newcommand{\dotcup}{\ensuremath{\mathaccent\cdot\cup}}
\newcommand{\qLRq}{\quad \Leftrightarrow \quad}
\newcommand{\qRq}{\quad \Rightarrow \quad}
\newcommand{\normal}{\mathrm{N}}

% left-right wrappers
\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\dtv}[2]{d_{\mathrm{TV}}(#1,#2)}       
\newcommand{\dchi}[2]{d_{\chi^2}(#1,#2)}           
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}

%%%%%%%%%%%% Fourier-specific macros %%%%%%%%%%%%

\newcommand{\conv}{*}
\newcommand{\bn}{\bits^n} \newcommand{\bitsn}{\bn}
\newcommand{\btb}{\co \bits^n \to \bits}
\newcommand{\bti}{\co \bits^n \to [-1,1]} \newcommand{\btI}{\bti}
\newcommand{\btR}{\co \bits^n \to \R}
\newcommand{\ftzo}{\co \F_2^n \to \{0,1\}}
\newcommand{\ftb}{\co \F_2^n \to \{-1,1\}}
\newcommand{\ftR}{\co \F_2^n \to \R}
\newcommand{\zotzo}{\co \zo^n \to \zo}
\newcommand{\true}{\mathsf{True}}       \newcommand{\True}{\true}
\newcommand{\false}{\mathsf{False}}     \newcommand{\False}{\false}
\newcommand{\dualF}{{\wh{\F_2^n}}}
\newcommand{\sumS}{\sum_{S \subseteq [n]}}


\newcommand{\Inf}{\mathbf{Inf}}
\newcommand{\Stab}{\mathbf{Stab}} \newcommand{\stab}{\Stab}
\newcommand{\bias}{\mathbf{bias}}
\newcommand{\NS}{\mathbf{NS}}
\newcommand{\Weight}[1]{\mathbf{W}^{#1}} \newcommand{\W}[1]{\Weight{#1}}
\newcommand{\TInf}{\mathbf{I}}   \newcommand{\Tinf}{\TInf}
\newcommand{\MaxInf}{\mathbf{MaxInf}}
\newcommand{\Ent}{\mathbf{Ent}}
\newcommand{\specsamp}[1]{\mathscr{S}_{#1}}
\newcommand{\D}{\mathrm{D}}
\newcommand{\uE}{\mathrm{E}}       % u for upright
\newcommand{\uP}{\mathrm{P}}       % u for upright
\newcommand{\uVar}{\mathrm{Var}}   % u for upright
\newcommand{\Lap}{\mathrm{L}}
\newcommand{\T}{\mathrm{T}}
\newcommand{\U}{\mathrm{U}}
\newcommand{\restr}[3]{#1_{#2 \mid #3}}             
\newcommand{\frestr}[3]{\mathrm{F}_{#1 \mid #2} #3} 
\newcommand{\snorm}[1]{\hat{\lV} #1 \hat{\rV}}
\newcommand{\sparsity}[1]{\mathrm{sparsity}(#1)}
\newcommand{\ssparsity}[1]{\mathrm{sparsity}(\wh{#1})}
\newcommand{\booldual}{\dagger}
\newcommand{\GIso}{\calU}       \newcommand{\Giso}{\GIso}

\newcommand{\DT}{{\mathrm{DT}}}
\newcommand{\DTsize}{{\mathrm{DT}_{\mathrm{size}}}}
\newcommand{\DNFsize}{{\mathrm{DNF}_{\mathrm{size}}}}
\newcommand{\DNFwidth}{{\mathrm{DNF}_{\mathrm{width}}}}

\newcommand{\distsq}{\mathrm{dist}^2}
\newcommand{\distsqzo}{\distsq_{[0,1]}}
\newcommand{\distsqint}{\distsq_{[-1,1]}}
\newcommand{\distzo}{\dist_{[0,1]}}
\newcommand{\distint}{\dist_{[-1,1]}}
\newcommand{\trunc}{\mathrm{trunc}}
\newcommand{\trunczo}{\trunc_{[0,1]}}
\newcommand{\truncint}{\trunc_{[-1,1]}}

\newcommand{\Krav}{\calK}
\newcommand{\krav}{K}

\newcommand{\GaussQuad}{\Lambda}       
\newcommand{\olPhi}{\ol{\Phi}}

\newcommand{\pbiased}[1]{\pi_{#1}}
\newcommand{\unif}{\pbiased{1/2}}

% words

\newcommand{\dvq}{Dictator-vs.-No-Notables test\xspace}
\newcommand{\dvqs}{Dictator-vs.-No-Notables tests\xspace}
\newcommand{\Hastad}{H{\aa}stad\xspace}  \newcommand{\hastad}{\Hastad}
\newcommand{\Holder}{H{\"o}lder\xspace}
\newcommand{\UG}{UG}


%%%%%%%%%%%% document-writing macros %%%%%%%%%%%%

%\newcommand{\ignore}[1]{*\marginpar{\tiny \em ignored part}}
\newcommand{\ignore}[1]{}

\newcommand{\noteryan}[1]{*\marginpar{\tiny *Note: \bf #1}}
%\newcommand{\noteryan}[1]{{\tiny [[#1]]}}
%\newcommand{\noteryan}[1]{}

\newcommand{\myfig}[4]{\begin{figure}[H] \centering \includegraphics[width=#1\textwidth]{#2} \caption{#3} \label{#4} \end{figure}}
