Homework 10:Review for FinalMay 9

COURSE WEBSITE: www.cs.umd.edu/$\sim$gasarch/858/858.html

1. (50 points) Assume there is a set of hash functions $H_{n,k}$ such that the following hold.
   1. $H_{n,k}$ has functions from $\bits n$ to $\bits k$.
   2. Arthur can pick an $h\in H_{n,k}$ randomly.
   3. For all $k,n$, for all $X\subseteq \bits n$, if Arthur picks $h\in H_{n,k}$ at random, and $S= \vert \{ x\in X \st h(x)=0^k \}\vert$, then $E(S)= \vert X\vert - 2^{-\sqrt{k}}$ and $Var(S) \le 2$.

   Let PROMISE$(\phi$) be `` $\char93 (\phi(x_1,\ldots,x_n)) \le 2^{n-1}$ OR $\char93 (\phi(x_1,\ldots,x_n)) \ge 2^{n-1}+n$''.

   Let $A = \{ \phi \st \char93 (\phi(x_1,\ldots,x_n)) \ge 2^{n-1}+n \}$ .

   Use the $H_{k,n}$ to come up with an AM protocol for $A$ assuming that, for all inputs $\phi$, PROMISE($\phi$) holds. Prove that it works.

   HINT: The answer should be of the following form (you need to fill in the blanks).

   PROTOCOL:

   1. Input( $\phi(x_1,\ldots,x_n))$ (We assume PROMISE $(\phi(x_1,\ldots,x_n)$ holds.)
   2. Arthur picks a random $h\in H_{k,n}$ where $k=XXX$. Arthur sends this $h$ to Merlin.
   3. Merlin sends Arthur YYY elements $z\in \bits n$.
   4. Arthur checks that, for each $z\in \bits n$ that Merlin send, ZZZ holds. If so, he accepts. If not he rejects.

   PROOF OF CORRECTNESS:

   If $\char93 \phi \ge 2^{n-1}+n$ then FILL THIS IN hence $\Prob(\hbox{ Arthur accepts}) \ge \frac{3}{4}$.

   If $\char93 \phi \le 2^{n-1}$ then FILL THIS IN hence $\Prob(\hbox{ Arthur accepts}) \le \frac{1}{4}$.

2. (50 points) Show that $PCP(5,\log n,\frac{1}{4}) \subseteq NP$.

3. (0 points- don't hand in) What is your favorite theorem from this course? Why?