Homework #4

May 24, 2010

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.

Problems

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.

Posted in Uncategorized | Leave a Comment »

Homework #3

May 3, 2010

Due: Wednesday, May 12, 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.

Problems

Each problem is worth 15 points unless otherwise noted.

  1. Show that any boolean function on n bits can be computed by a circuit of size less than 1000 \cdot 2^n/n. Hint: In class we saw a recursive way to give a circuit of size O(2^n) for any boolean function. Try to use the same method, but stop after n-logn levels of the recursion. At this point, use the fact that there are only a few functions on log n bits, to complete the evaluation of the overall function.
  2. A language L \subset \{0,1\}^* is sparse if there is a polynomial p such that |L \cap \{0,1\}^n | \leq p(n) for every n. Show that every sparse language is in P/poly.
  3. Call a multiset of n bit strings P \epsilon-pseudorandom for circuits of size s, if for every circuit C (with one bit output) of size s, C cannot distinguish a random element from P from a truly random string, in the following sense. If X is a uniformly random element of P, and U is a uniformly random n bit string, then |\Pr[C(X) = 1] - \Pr[C(U)=1] | < \epsilon. Show that for every s, n, there is an 1/10-pseudorandom set with |P| \leq poly(s). Hint: try to pick P randomly, and then argue that P simultaneously fools all circuits of size s with positive probability.
  4. Suppose there is a randomized polynomial time algorithm that takes as input a 3-CNF, and outputs another 3-CNF with the property that if the input is satisfiable, then the output is not satisfiable with probability at least 2/3, and if the input is unsatisfiable, then the output is satisfiable with probability at least 2/3. Show that this would imply that the polynomial hierarchy collapses to \Sigma_3^p. Hint: follow the proof that if NP has polynomial sized circuits, then the hierarchy collapses to the second level.

Posted in Uncategorized | 4 Comments »

Homework #2

April 19, 2010

Due: Monday, May 3, 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.

Problems

Each problem is worth 15 points unless otherwise noted.

  1. Let A be the language of properly nested parentheses. For example (()) and (()()(())) are in A, but )( is not. Show that A is in L.
  2. Let CONNECTED denote the language consisting of directed graphs which are strongly connected: there is a path from a to b, for every pair of vertices a,b. Show that CONNECTED is NL-complete.
  3. An undirected graph is bipartite if the vertices can be partitioned into two sets such that all edges go from a node in one set to a node in the other. A graph is bipartite if and only if it does not have any cycles of odd length. Let BIPARTITE denote the language consisting of bipartite graphs. Show that BIPARTITE \in NL.
  4. Show that SAT \notin TISP(n^c, n^d) for all constants c,d such that c(c+d)<2.
  5. If S = \{ S_1,S_2,\dotsc,S_m \} is a collection of subsets of a finite set U, the VC dimension of S is the size of the largest set X \subset U such that for every X' \subset X, there is a set S_i in S for which S_i \cap X = X'. A boolean circuit \mathcal{C} represents collection S if S_i consists of exactly those elements x \in U for which C(i,x) = 1. Define the language VC-DIMENSION to consist of those pairs <C,k> such that C is a circuit representing a family of VC dimension at least k. Show that VC-DIMENSION is in \Sigma_3^p, and is complete for this class.

Posted in Uncategorized | Leave a Comment »

Homework #1

April 5, 2010

Due: Monday, April 19, 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.

Problems

Each problem is worth 15 points unless otherwise noted.

  1. Exercise 2.8 from the text: Let HALT be the Halting Language defined in Theorem 1.11 of the text: HALT = \{ a,x | M_a(x) \text{ halts in a finite number of steps} \}. Show that HALT is NP-hard. Is it NP-complete?
  2. Exercise 2.10 from the text: Suppose L_1, L_2 are in NP. Then is L_1 \cup L_2 in NP? What about L_1 \cap L_2?
  3. Exercise 2.15 from the text: A clique of an undirected graph is a set of vertices in which every two vertices have an edge between them. A vertex cover is a subset such that every edge of the graph is incident to one of the vertices from the set. Let CLIQUE be language \{G,k | \text{ the graph G has a clique of size k } \} , and let VERTEX COVER be the language \{ G,k | \text{the graph G has a vertex cover of size k} \} . Prove that both of these problems are NP-complete.
  4. Exercise 3.9 from the text: Suppose we pick a random language C by choosing every string to be in C independently with probability 1/2. Prove that with high probability P^C is not the same as NP^C .
  5. A digital signature scheme is a triple of randomized polynomial time algorithms: Generate, Sign, and Check, with the following properties. On input  1^n , Generate outputs a pair of strings (public, secret), such that for any message m, Check(m,Sign(m,secret),public) always outputs 1, yet for any polynomial time algorithm A, the probability that Check(m,A(m,public),public) outputs 1 is at most O(n^{-100}) . Show that such a scheme cannot exist if P=NP.

Posted in Homework | 1 Comment »

Welcome to CSE531

March 29, 2010

This blog will be used as the class website.

Posted in Uncategorized | Leave a Comment »