CS 535: Complexity Theory, Fall 2020 Homework 7
Due: 2:00AM, Saturday, November 7, 2020.
Reminder. Homework must be typeset with LATEX preferred. Make sure you understand the course collaboration and honesty policy before beginning this assignment. Collaboration is permitted, but you must write the solutions by yourself without assistance. You must also identify your collaborators. Assignments missing a collaboration statement will not be accepted. Getting solutions from outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Problem 0 (Term Paper). Your term paper topic and partner (if applicable) are due on Gradescope at the same time this homework assignment is. Instructions for the term paper are here: https://cs-people.bu.edu/mbun/courses/535_F20/handouts/term_paper.pdf and a list of suggested topics is here: https://piazza.com/class/keda2wyieyz10e?cid= 277.
Problem 1 (Circuit Lower Bounds for PH). In this problem, you will prove that PH can compute languages with high circuit complexity. Specifically, you will show that for every integer k ≥ 1, there is a language in Σp2 that cannot be computed by circuits of size at most nk.
(a) Show that for every input length n, there exists a function f : {0, 1}n → {0, 1} that is computed by a circuit of size at most 20nk, but not computed by any circuit of size at most nk. Hint: Use the nonuniform hierarchy theorem (Theorem 6.22 in Arora-Barak). (2 points)
(b) Let C,C′ be circuits, both on n-bit inputs. Say that C′ comes lexicographically before C, written C′