%You can leave alone everything before Line 84.
\def\draft{1}

\documentclass{article}
\usepackage{url,amsfonts, amsmath, amssymb, amsthm, color}
% Page layout
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\parindent}{1pc}
\newcommand{\shortbar}{\begin{center}\rule{5ex}{0.1pt}\end{center}}
%\renewcommand{\baselinestretch}{1.1}
% Macros for course info
\newcommand{\courseNumber}{CMSC 652}
\newcommand{\courseTitle}{Complexity Theory}
\newcommand{\semester}{Fall 2017}
% Theorem-like structures are numbered within SECTION units
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{statement}[theorem]{Statement}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{fact}{Fact}
%definition style
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}{Example}
%\newtheorem{problem}{Problem}
\newtheorem{exercise}{Exercise}
\newtheorem{algorithm}{Algorithm}
%remark style
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{reduction}[theorem]{Reduction}
%\newtheorem{question}[theorem]{Question}
\newtheorem{question}{Question}
%\newtheorem{claim}[theorem]{Claim}
%
% Proof-making commands and environments
\newcommand{\beginproof}{\medskip\noindent{\bf Proof.~}}
\newcommand{\beginproofof}[1]{\medskip\noindent{\bf Proof of #1.~}}
\newcommand{\finishproof}{\hspace{0.2ex}\rule{1ex}{1ex}}
\newenvironment{problem}[1]{\medskip\noindent{\bf Problem #1.~}}{\shortbar}
\newenvironment{solution}[1]{\medskip\noindent{\bf Solution #1.~}}{\shortbar}

\ifnum\draft=1
\newcommand{\note}[1]{{\color{blue} #1}}
\newcommand{\cmt}[1]{{\color{red} #1}} 
\else
\newcommand{\note}[1]{{}}
\newcommand{\cmt}[1]{{#1}} 
\fi


%====header======
\newcommand{\solutions}[3]{
%\renewcommand{\thesolution}{{\large #2}.\arabic{problem}}
\vspace{-2ex}
\begin{center}
{\small  \courseNumber, \courseTitle
\hfill {\large \bf {Due: #1} }\\
\semester, University of Maryland \hfill
{\em Date: #3}}\\
\vspace{-1ex}
\hrulefill\\
\vspace{4ex}
{\Large #2}\\
\vspace{2ex}
\end{center}
\shortbar
\vspace{3ex}
}

\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\solutions{November 3th, 2017}{Assignment 4}{\today}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Begin the solution for each problem by
% \begin{solution}{Problem Number} and ends it with \end{solution}
%
% the solution for Problem 1

\textbf{You must submit it electronically to ELMS}. This is a group assignment. Every group only needs to submit one solution. Group members get the same credit for the group submission. 

This assignment is 7\% in your total points. For the simplicity of the grading, the total points for the assignment is 70. 

\begin{problem}{1 [20 pts]}
Prove the following relationships among RP, CoRP and ZPP.
\begin{itemize}
  \item(1) [10 pts] Prove that $L \in$ ZPP iff there exists an expected polynomial-time Turing machine $M$ such that
  \[
   Pr[M(x) =\chi_L(x)] = 1,
  \]
  where $\chi_L(x)=1$ if $x \in L$ and otherwise $\chi_L(x)=0$. Note that in the lecture the definition (for ZPP) is that a probabilistic TM M that runs in polynomial time, and outputs either a correct answer (with probability at least 1/2) or "I don't know".
  \item(2) [10 pts]  ZPP=RP$\bigcap$CoRP.  
\end{itemize}
\end{problem}

\begin{problem}{2 [20 pts]}
Let $A$ be a symmetric stochastic matrix (i.e., $A=A^T$, and every row and column of A has nonnegative entries summing up to 1). Prove that the spectral norm of $A$ (denoted $\|A\|$) is at most 1. Note that the spectral norm of $A$ is defined by the maximum of $\|Ax\|$ over unit vector $x$ (i.e., $\|x\|=1$). 
\end{problem}

\begin{problem}{3 [30 pts]}
In this exercise, we show how to derive a randomness-efficient error-reduction procedure for BPP. Note that in the lecture, we only show how to do so for RP. Let $G$ be an $(n, d, \lambda)$ graph, and $\mathcal{B} \subseteq [n]$ ($|\mathcal{B}|\leq \beta n$) for some $\beta \in (0,1)$. Let $X_1, \cdots, X_k$ be random variables denoting a $k-1$ step random walk in $G$ from $X_1$, where $X_1$ is chosen uniformly in $[n]$. 

\begin{itemize}
  \item(1) [10 pts] For every subset $I \subseteq[k]$, 
  \[
     Pr[ \forall_{i \in I} X_i \in B] \leq ((1-\lambda)\sqrt{\beta}+\lambda)^{|I|-1}.
  \]
  \item(2) [10 pts] Conclude that if $|B|<n/100$ and $\lambda<1/100$, then the probability that there exists a subset $I \subseteq [k]$ such that $|I|>k/10$ and $\forall_{i \in I} X_i \in B$ is at most $2^{-k/100}$. 
  \item(3) [10 pts] Use this to show a procedure that transforms every BPP algorithm $A$ that uses $m$ coins and decides a language $L$ with probability 0.99 into an algorithm $B$ that uses $m+O(k)$ coins and decides the language $L$ with probability $1-2^{-k}$. 
\end{itemize} 
\end{problem}


\end{document}
