## 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.

### 4 Responses to “Homework #3”

1. Rolfe Says:

In problem 2 is it supposed to be $|L \cap \{0,1\}^n| \leq p(n)$?

2. Gilbert Bernstein Says:

On 3, does epsilon depend on anything? If not, then doesn’t this force the two probabilities to be equal? Doesn’t this further permit the construction of counterexamples for small circuits? (say quadratic size)

• anuprao Says:

Hi Gilbert, you are right, the size of the set should depend on epsilon. In general you can find a set of size poly(s, 1/epsilon). Also, I meant for P to be a multiset (or else the size may depend on n). I will send an email about this problem soon.