In [Vollmer]: 1.16, 1.17, 1.19, 1.20, 2.4, 2.8

In [Trevisan]: Chapter 1, problem 3 (We'll do this one as a class project; discuss it among yourselves.)

In [Vollmer]: 3.9, 3.14

In [Trevisan]: Chapter 2, problems 1,2

Chapter 3, problems 1,2

Chapter 4, problem 3

In [Vollmer]: 4.22, 4.23, 4.46, 6.7

In [Trevisan]: Chapter 5, problems 2,3

Show that ParityP with a BPP oracle can be simulated by BPP with a ParityP oracle. (I don't want to bother with superscripts on this page... If you want to see this written more carefully, look at the notes from 1998 on Toda's Theorem. Right after Lemma 2 in those notes, look at what is referred to as "Problem 5 in our assignment 6".)

In [Trevisan]:

Chapter 10, problems 2,3 (treat problem 3 as a group project)

Chapter 11, problems 1,2

Chapter 13, problems 1,2

1. In [Trevisan]: Chapter 14, problem 1

2. We showed that if there is a language in E that requires circuits of size 2^{cn} for some c>0, then there is a pseudorandom generator taking seeds of size O(log m) and producing pseudorandom output of length m, that is secure against circuits of size 2m. Show that the converse also holds.

3. The Minimum Circuit Size Problem (MCSP) is defined as {f : f has a circuit of size at most square.root(|f|)}, where f is a Boolean function, given by its truth table. (This is not quite the usual definition of MCSP, but it is sufficient for our purposes.) Show that MCSP is in NP.

Note that all strings that are in MCSP have length that is a power of 2. In order to do problem 5 below, it will be useful to modify this property slightly. We can consider

4. Show that BPP is contained in ZPP^MCSP. (This improves the result that BPP is in Sigma_2 in two ways, since MCSP is not known to be NP complete, and since ZPP seems to be a ``small'' subclass of NP.) [For this problem, you may assume (without proof) the following observation: The "worst-case-to-average-case" reduction for E that is presented in Trevisan's notes, can be rephrased to prove the following result: for any epsilon > 0, there is a delta > 0 and a polynomial-time transformation T with the property that, if f is the truth-table of a function that requires circuits of size at least 2^{epsilon n}, then T(f) is the truth-table of a function with hardness 2^{delta n}. T(f) is an error-correcting encoding of the function f.]

5. Show that if MCSP is complete for NP under ``length-increasing'' polynomial-time reductions, then BPP = P. (A many-one reduction f is length-increasing if, for all x, f(x) has more symbols than x has. All of the NP-complete problems in [Garey,Johnson] are complete under length-increasing reductions.)