%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 17th, 2017}{Assignment 5}{\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]}
%Show that the random walk idea for solving connectivity does not work for directed graphs. In other words, describe a directed graph on $n$ vertices and a starting point $s$ such that the expected time to reach $t$ is $\Omega(2^n)$, even though there is a directed path from $s$ to $t$. 
%\end{problem}

\begin{problem}{1 [20 pts]}
Let $k\leq n$. Prove that the following family $\mathcal{H}_{n,k}$ is a collection of pairwise independent functions from $\{0,1\}^n$ to $\{0,1\}^k$: identify $\{0,1\}$ with the field of $GF(2)$. For every $k\times n$ matrix $A$ with entries in GF(2), and $\mathbf{b}\in GF(2)^k$, $\mathcal{H}_{n,k}$ contains the function $h_{A, \mathbf{b}}: GF(2)^n \rightarrow GF(2)^k$ defined as $h_{A, \mathbf{b}}(x)=Ax+\mathbf{b}$. 
\end{problem}

\begin{problem}{2 [20 pts]}
Prove that these exists an AM protocol such that: given any set $S\subseteq \{0, 1\}^n$ either $|S|\geq K$ or $|S|\leq K/8$ for some $K=2^k$ and $k\leq n$, that AM protocol can tell which case it is with perfect completeness and constant soundness. (In the lecture, we talked about an AM protocol with only constant (but not perfect) completeness.)
\end{problem}

\begin{problem}{3 [30 pts]}
Consider the follow (true) TQBF statement 
\[
 \phi: \forall x_1 \exists x_2: (x_1\vee \bar{x}_2) \wedge (\bar{x}_1\vee x_2)
\]
\begin{itemize}
\item (1) [10 pts] Write out the arithmetization $\Phi$ of $\phi$, and prove that 
\[
  \prod_{x_1 \in \{0,1\}} R_{x_1} \coprod_{x_2 \in \{0,1\}} R_{x_1} R_{x_2} \Phi(x_1,x_2) =1 \mod 11,
\]
where $R_x$ denotes the "degree reduction" operation applied to variable $x$ (i.e., $x^k=x$ for any $k>0$ defined in Katz's lecture 19). 
\item (2) [20 pts] Explicitly write out the entire interactive proof for the statement above, following exactly the template given in class. Work modulo q = 11, and assume that in the first iteration the verifier chooses "random value" 1, then "random value" 2, "random value" 3, and so on. (These choices of the random numbers are just for the convenience of grading. In a real execution of the protocol, the verifier would of course need to choose the random values at random, and we would have to take q larger than 11.)
\end{itemize}
\end{problem}


\end{document}
