\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext,amssymb}
\usepackage{amsmath}
\usepackage{german}
\usepackage{graphicx}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{10}
\newcommand{\ABGABEDATUM}{on 5. July 2016 in the tutorial session}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Problem~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\eps}{\varepsilon}
\newcommand{\N}{\mathbb{N}}
\newcommand{\F}{\mathbb{F}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Assignment on 

\smallskip
\noindent
\large
\textbf{Computational Complexity Theory}\hfill SoSe 2016 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Claudia Dieckmann

\medskip\hrule

\smallskip
\noindent
\textbf{Due} \ABGABEDATUM

\vskip 0.5cm


\begin{description}
\AUFGABE {Sipser-G\'acs-Lautemann Theorem} {10 points}

In this problem we look at an alternative proof for
$\text{BPP} \subseteq \Sigma_2^p \cap \Pi_2^p$ that uses
hashing. 

Let $L \in \text{BPP}$, $d \geq 2$ be a constant, and $V$ 
a deterministic polynomial time verifier for $L$ such that
for any $w \in \{0,1\}^*$,  if we set
$n := |w|$ and $m := n^d$, then
\begin{align*}
 w \in L &\Rightarrow |\{ r \in \{0,1\}^m \mid  V(w, r) \text{ accepts} \}|
    \geq (1-2^{-n}) 2^{m};\\
 w \not\in L &\Rightarrow |\{ r \in \{0,1\}^m \mid  V(w, r) 
 \text{ accepts} \}| \leq 2^{-n} 2^{m}.
\end{align*}
Set $A_w := \{ r \in \{0,1\}^m \mid  V(w, r) \text{ accepts} \}$. We use 
hashing to distinguish whether $A_w$ is large or small.

Set $a := \lceil n/2 \rceil$.
Let $\F_2$ be the field with two elements, and let $V := \F_2^m$ and 
$W := \F_2^{m-a}$, considered as vector spaces. A \emph{hash function} is
a linear map from $V$ to $W$, i.e., an $(m-a) \times m$ matrix
with entries from $\F_2$.

\textbf{Task 1.}
Let $x,y \in V$, $x \neq y$. Show that $\Pr_h[h(x) = h(y)] = 2^{-m+a}$,
where $h$ is a random hash function (i.e., each entry of the matrix $h$
is chosen randomly in $\{0,1\}$).

Set $r := \lceil 2m/n \rceil$. We would like to show that
\begin{multline}\label{equ:condition}
  w \in L \Leftrightarrow
    \forall h_1, \dots, h_r  \exists v, w_1, \dots, w_r, v \neq w_1, 
    \dots, w_r:\\
    \bigwedge_{i = 1}^r
      (v \in A_w \wedge w_i \in A_w \wedge h_i(v) = h_i(w_i)),
\end{multline}
where $h_1, \dots, h_r$ are hash functions and 
$v, w_1, \dots, w_r \in \F_2^m$ with
$v \not\in \{w_1, \dots, w_r\}$.

\textbf{Task 2.} Show that (\ref{equ:condition}) is a $\Pi_2^p$ statement.
Give an intuitive explanation for (\ref{equ:condition}).

\textbf{Task 3.} Show the ``$\Rightarrow$'' direction of (\ref{equ:condition}).

\emph{Hint}: Fix $h_1, \dots, h_r$. For each $h_i$, count how many elements
  in $A_w$ can have no collision under $h_i$. Conclude that there is an
  element $v$ that collides under each $h_i$.

\textbf{Task 4.} Show the ``$\Leftarrow$'' direction of (\ref{equ:condition}).

\emph{Hint}: Show the contrapositive
\begin{multline*}
  w \not\in L \Rightarrow
    \exists h_1, \dots, h_r  \forall v, w_1, \dots, w_r, v \neq w_1, \dots, w_r:  \\
      \bigvee_{i = 1}^r (v \not\in A_w \vee w_i \not\in A_w \vee h_i(v) \neq h_i(w_i)).
\end{multline*}
Choose $h_1, \dots, h_r$ randomly. Fix $v, w_1, \dots, w_r \in A_w$ such
that $v \not\in \{w_1, \dots, w_r\}$. What
is the probability, that $h_i(v) = h_i(w_i)$ for all $i = 1, \dots, r$?
How many possible choices for $v, w_1, \dots, w_r \in A_w$ are there? Use the probabilistic
method to prove that appropriate $h_1, \dots, h_r$ exist.


\textbf{Task 5.} Conclude that $\text{BPP} \subseteq \Sigma^p_2 \cap \Pi_2^p$.
\AUFGABE {dIP} {10 points}

Show that $\text{dIP} = \text{NP}$.

\AUFGABE {IP} {10 points}

Show that $\text{IP} \subseteq \text{PSPACE}$.

\end{description}
\end{document}
