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

\newcommand{\ZETTELNUMMER}{11}
\newcommand{\ABGABEDATUM}{on 12. 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
\\
This is the last problem set.
\vskip 0.5cm


\begin{description}
\AUFGABE{Goldwasser-Sipser Set Lowerbound} {10 points}
\begin{enumerate}
\item
  Let $n \in \N$. Define 
  $\mathcal{H}_{n,n} := \{h_{a,b}\}_{a,b \in \text{GF}(2^n)}$, where for 
  $a,b \in \text{GF}(2^n)$ we set 
  $h_{a,b}(x) = ax+b$ for all $x \in \text{GF}(2^n)$ (recall that
  $\text{GF}(2^n)$ is the finite field with $2^n$ elements).
  Show that $\mathcal{H}_{n,n}$ is a pairwise independent family of hash 
  functions.
\item
  For $k \in \N$, define $\mathcal{H}_{n,k}$ as the family obtained from
  $\mathcal{H}_{n,n}$ by adding $k-n$  zeros to the input if $k > n$ or by
  dropping $n-k$ bits from the output if $k < n$. Show that $\mathcal{H}_{n,k}$
  is a pairwise independent family of hash functions.
\item 
  Work out the details of the Goldwasser-Sipser protocol. In particular,
  use Chernoff-bounds to estimate the required number of samples.
\end{enumerate}

\AUFGABE{Chernoff-Bounds}{10 points}
\begin{enumerate}
\item 
  Read the notes on Chernoff-bounds on the website. Which proof technique
  do you like best? Why?
\item
  Suppose we are given a coin with unknown probability $p > 0$ of coming 
  up heads.  Let $\eps > 0$ and $\delta > 0$. 
  Devise an algorithm that gives an \emph{additive} $\eps$ approximation 
  for $p$ with probability at least $1-\delta$ (i.e., we want an 
  estimate $\tilde p$ such that $\Pr[|p-\tilde p| > \eps] \leq \delta$). 
  Repeat for the case of multiplicative error 
  (i.e., $\Pr[|p-\tilde p| > \eps p] \leq \delta$).
  What is the running time?
\end{enumerate}

\AUFGABE{Set Lowerbound with Perfect Completeness}{10 points}


(This is Problem~8.5 in Arora-Barak.)
Show that there exists a perfectly complete $\text{AM}[O(1)]$ protocol
for proving a lower bound on set size.


\emph{Hint}: First note that in the Goldwasser-Sipser protocol, we can have
  the prover choose the hash function. Consider the easier case of constructing
  a protocol to distinguish between the case $|S| \geq K$ and $|S| \leq K/c$,
  where $c \geq 2$ can even be a function of the input size. If $c$ is large
  enough, we can allow the prover to use \emph{several} hash functions
  $h_1, \dots, k_\ell$, and it can be proven that if $\ell$ is large enough,
  we will have $\bigcup_i h_i(S) = \{0,1\}^k$ for large $S$. The gap
  can be increased by considering instead of $S$ the set $S^z$, i.e., the
  $z$ times Cartesian product of $S$.
\end{description}
\end{document}
