Lesson 1

Basic Problems.

1. (10 points) Prove that, for any two (finite) complete bases \(\Omega_{1}\) and \(\Omega_{2}\), there exists a constant \(c\), such that, for any Boolean function \(f\), \[\operatorname{size}_{\Omega_1}(f) \le c \cdot \operatorname{size}_{\Omega_2}(f).\]
2. (10 points) Construct a circuit of size \(O(n)\) for the function \(\operatorname{GREATER}(x_{0}, \dotsc, x_{n-1}, y_{0}, \dotsc, y_{n-1}) \in B_{2n}\) that takes as input two \(n\)-bit numbers and outputs one if and only if the first is strictly greater than the second: \[\operatorname{GREATER}(x_{0}, \dotsc, x_{n-1}, y_{0}, \dotsc, y_{n-1}) = \left[\sum_{i=0}^{n-1}x_{i}2^{i} > \sum_{i=0}^{n-1}y_{i}2^{i}\right].\]
   Hint:

   You may want to use the divide-and-conquer approach.
3. (10 points) Given a circuit of size \(s\) with a single output bit, construct a formula in CNF with \(O(s)\) clauses that is satisfiable if and only if the original circuit is satisfiable.
4. (15 points) Construct a circuit of size \(O(n)\) and depth \(O(\log n)\) for the \(\operatorname{GREATER}\in B_{2n}\) function.
5. (15 points) Design a circuit of size \(2 \cdot 2^{m}\) with \(2^{m}\) outputs, implementing all \(2^{m}\) possible conjunctions of length \(m\). For example, for \(m=2\), this circuit computes \(x_{1}x_{2}\), \(\overline{x_1}x_{2}\), \(x_{1}\overline{x_2}\), \(\overline{x_1}\overline{x_2}\).
6. (15 points) Imagine yourself as an engineer: you are given a circuit (e.g., for multiplying long numbers) of size \(s_{1}\) over \(n\) variables and are asked to come up with a smaller circuit that computes the same thing. Assume that you've designed a circuit of size \(s_{2}<s_{1}\). Now, you would like to convince everybody that your new circuit computes the same as the original circuit. One possibility would be to go through all \(2^{n}\) input assignments, but this does not scale well: already for \(n=200\), this is impractical.

   Show that one can construct a formula in CNF with \(O(s_{1} + s_{2}+n)\) variables that is unsatisfiable if and only if the two circuits compute the same function.

7. (15 points) Let \(f = (f_{1}, \dotsc, f_{m})\), where \(f_{i} \in B_{n}\), i.e., \(f \colon \{ 0, 1 \}^{n}\to \{ 0, 1 \}^{m}\), and all \(f_{i}\) are pairwise distinct. Prove that \[\operatorname{size}_{B_2}(f) \ge \min_{i \in [m]}\{ \operatorname{size}_{B_2}(f_{i}) \} + (m - 1).\]
8. (15 points) Prove that \(\operatorname{size}_{B_2}(\operatorname{THR}_{n}^{2}) \leq 3n - 5\).
9. (15 points) Prove that \(\operatorname{size}_{B_2}(\operatorname{THR}_{n}^{2}) \ge 2n - O(1)\).
   Hint:

   Is it possible that all input variables have out-degree equal to one?