Homework due February 9
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.)
Homework due February 23
In [Vollmer]: 3.9, 3.14
In [Trevisan]: Chapter 2, problems 1,2
Chapter 3, problems 1,2
Chapter 4, problem 3
Homework due March 9
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".)
Homework due April 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
Homework due April 20
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 any string to be
an encoding of a truth table, as follows. If 2^m < |x| < 2^{m+1}, then
consider x to be an encoding of the function f on m+1 variables whose
truth-table is of the form x0...0.
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.)