Problem Set 3

tags: pset

Instructions

• $LATEX$ your solutions and submit them on Moodle.
• You are welcome to discuss the ideas involved in solving the problems amongst yourselves, but the solutions that you write must be your own. If you have doubts regarding what this means, please talk to me.
• Always cite sources that gave you the idea for solving a problem, including external sources. If you discussed with a friend, please mention his/her name. This will not affect your grades.
• Try to write brief answers. Only write what is necessary and sufficient.
• If you don't know an answer, just write what you know and leave the rest. Better still, discuss with me if you are stuck.

Problem 1 [10 marks]

Prove that if there exists a

$\delta$-density distribution

$H$ such that

$\underset{x\sim H}{Pr}[C(x)=f(x)]\le 1/2+ϵ$ for every circuit

$C$ of size

$S$ with

$S\le \sqrt{{ϵ}^2\delta 2^n/100}$, then there exists a subset

$I\subseteq \{0,1{\}}^n$ of size at least

$\delta 2^n/2$ such that

$$\underset{x{\in }_{r}I}{Pr}[C(x)=f(x)]\le \frac{1}{2}+ϵ$$
for every circuit

$C$ of size at most

$S$.

(This is Exercise 19.2 in [AB]. See the hint for this problem.)

Problem 2 [10 marks]

Show that if there exists a

$f\in DTIME(2^{O(n)})$ and

$ϵ>0$ such that

$H_{avg}(f)(n)\ge 2^{ϵn}$ for every

$n\in \mathbb{N}$, then

$MA=NP$.

(This is Exercise 20.6 in [AB]. See the hint for this problem.)

Problem 3 [5 marks]

The class MIP consists of languages that can be decided by an interactive proof with a single verifier and two provers. In each round of communication, the verifier sends messages to the the provers. The provers respond to these messages, but the provers are not allowed to communicate with each other.

Show that MIP

$\subseteq$ NEXP.

Problem 4 [10 marks]

Show that if we define MIP to be the languages decided by an interactive proof between a probabilistic verifier and a polynomial number of provers, then there is a protocol for the language that has exactly two provers.

(This is exercise 8.12 in [AB]. See the hint for this problem.)