HW#4 --- last modified February 10 2019 21:57:31..
Solution set.
Due date: Dec 7
Files to be submitted:
Hw4.zip
Purpose: To learn more about circuits, lower bounds proofs, random computation models,
and interactive proofs.
Related Course Outcomes:
The main course outcomes covered by this assignment are:
LO4 -- Know properties of the randomized classes RP, BPP.
LO6 -- Be able to explain interactive proof characterizations of classes like PSPACE.
LO7 -- Explain at least one circuit lower bound technique such as Razborov's techniques for monotone circuits or switching lemma techniques
Specification:
This homework consists in doing the following problems:
- Prove that the language `{langle x, sqrt(x) rangle | \mbox(string ) x \mbox( encodes a natural number in binary)}` is
in `NC`.
- Show `BPP` is closed under unions, intersection, and complements of its members.
- Do Exercise 7.4 out of the book concerning error reduction in `RP`.
- Do Exercise 8.1 about `IP` in the book.
- Do Exercise 14.6 out of the book concerning Razborov Smolensky lower bounds.
On the day your homework is due I will ask each group to present one problem to me in class.
If you scored above 8 on Hw2 and you work for Hw3 with someone who scored below 8 on Hw2, I will give you a 1pt bonus. Similarly, if you scored below 8 on Hw2 and you work for Hw3 with someone who scored above 8 on Hw2, I will give you a 1pt bonus. Be advised though that all group members must be prepared to answer any question on class presentation day.
Point Breakdown
Five problems above (1.5 pts each - 1.5pts, completely correct; 1pt, missing minor details, 0.5pt, on the right track; 0 confused or wrong. |
7.5pts
|
Class presentation (Write-up clear, 1.5pts; all group members could answer brief questions about the problem intelligently, 1pt). |
2.5pts
|
Total | 10pts |
|