Homework #4

Due: Wednesday, June 2, at the beginning of class. Turn in physically or by email to Thach.

Remember to take a look at the grading guidelines.

In solving the problem sets, you are allowed to collaborate with fellow students taking the class, but remember that each submission can have at most one author. If you do collaborate in any way, you must acknowledge, for each problem, the people you worked with on that problem.

The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools.  Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.

Most of the problems only require one or two key ideas for their solution.  It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details.

A final piece of advice:  Start working on the problem sets early!  Don’t wait until the day (or few days) before they’re due.


Each problem is worth 15 points.

  1. Prove that for every AM[2] protocol for a language L, if the prover and the verifier repeat the protocol k times in parallel (verifier runs k independent random strings for each message) and the verifier accepts only if all k copies accept, then the probability that the verifier accepts x \notin L is at most (1/3)^k. (Note that you cannot assume the prover is acting independently in each execution.)
  2. Prove that for every constant k \geq 2, AM[k+1] \subseteq AM[k]. Hint: first prove that MAM \subseteq AM by repeating the proof in parallel and using the union bound. Then argue about general proofs.
  3. Show that computing the permanent for matrices with integer entries is in FP^{\#SAT}.
  4. Define SimpleIP to the class of languages that have an interactive protocol where the prover sends a single message and then the verifier makes an accept/reject decision based on this message (so there is in fact no interaction). Prove that SimpleIP is unlikely to equal IP by showing SimpleIP \subseteq \Sigma^P_2. Hint: Try to use the same ideas as in the proof that BPP is in the second level of the polynomial hierarchy.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: