Boolean Circuits · Theory Problems
Lesson 2
Advanced Problems.
- (20 points) A function \(f \in B_{n}\) is called symmetric if its output remains unchanged when the inputs are permuted (thus, the result depends only on the number of ones in the input). Prove \(\operatorname{size}_{B_2}(f) \le 5n+o(n)\).
- (20 points) Construct a circuit of size \(O(n^{\log_2 3})\) that computes the product of two \(n\)-bit numbers.
Hint:
You may draw inspiration from Karatsuba's algorithm. - (20 points) Design a circuit of size \(O(n^{3} \log n)\) that takes as input the adjacency matrix of a directed graph with \(n\) vertices and checks whether the graph is strongly connected.
- (20 points) Let \(n \le s \le \frac{2^n}{n^2}\). Prove that, for any sufficiently large \(n\), there exists \(f \in B_{n}\) such that \(s < \operatorname{size}_{B_2}(f) \le s + n\).
- (20 points) Prove that \(\operatorname{size}_{B_2}(\operatorname{THR}_{n}^{2}) \le 2n + o(n)\).
- (20 points) The function \[\operatorname{SORT}_{n}: \{0,1\}^{n}\to \{0,1\}^{n}\] orders the input bits in non-increasing order. Prove that \[\operatorname{size}_{B_2}(\operatorname{SORT}_{n}) \leq 7n + o(n).\]
Hint:
Recall that any symmetric function with one output gate can be computed by a circuit of size \(5n + o(n)\). - (20 points) An arithmetic circuit \(C\) over a ring \(R\) and variables \(x_{1}, \dotsc, x_{n}\) is a directed acyclic graph with nodes of in-degree zero or two. The in-degree zero nodes are labeled either by variables \(x_{i}\) or elements of \(R\), whereas the in-degree two nodes are labeled by either \(+\) or \(\times\). Every gate of out-degree zero is called an output gate. A single-output arithmetic circuit \(C\) over \(R\) computes a polynomial over \(R\) in a natural way. We say that \(C\) computes a polynomial \(P(x_{1}, \dotsc ,x_{n})\) if the two polynomials are identical (as opposed to saying that \(C\) computes \(P\) if the two polynomials agree on every assignment of \((x_{1},…,x_{n})\in R^{n}\)). We define the size of \(C\) as the number of edges in it, and the arithmetic circuit complexity of a polynomial as the minimum size of a circuit computing it.
Show that, over the ring \(R=\mathbb{F}_{2}\) and on Boolean inputs, the class of functions computable by Boolean circuits of polynomial size coincides with the class of functions computable by arithmetic circuits of polynomial size.
- (20 points) We know that the addition of two \(n\)-bit numbers can be computed by a circuit of size \(O(n)\): \(\operatorname{size}(\operatorname{ADD}_{n})=O(n)\). Show that there also exists a circuit of size \(O(n)\) and depth \(O(\log n)\).
Hint:
Forget about circuits for a moment and think about designing a parallel algorithm with a polynomial number of processors. Given a sequence \(x_{0}, \dotsc, x_{n - 1}\), the algorithm should compute the prefix array \(a_{0} = x_{0}, a_{1} = a_{0} + x_{1}, \dotsc, a_{n - 1}= a_{n - 2}+ x_{n - 1}\). Ensure that each processor performs at most \(O(\log n)\) steps, while the total workload is \(O(n)\). Then, consider how such a parallel algorithm can guide the construction of a circuit for \(\operatorname{ADD}_{n}\). - (20 points) The multiplexer function \(\operatorname{MUX}_{n} \in B_{n+k}\), where \(n = 2^{k}\), is defined as follows: \[\operatorname{MUX}_{n}(x_{0}, \dotsc, x_{k-1}, y_{0}, \dotsc, y_{n-1}) = y_{\ell},\] where \(0 \le \ell < n\) is the integer whose binary representation is \((x_{0}, \dotsc, x_{k-1})\). In other words, it selects the \(x\)-th bit of \(y\).
Prove that \(\operatorname{size}_{B_2}(\operatorname{MUX}_{n}) \le 2n + o(n)\).
- (20 points) Present an algorithm which, given a graph with \(n\) vertices and \(m\) edges, and an integer \(k = k(n, m)\), constructs in time \(O(n + m)\) a circuit with \(O(n)\) inputs, such that the circuit is satisfiable if and only if the graph contains a clique of size at least \(k\).
- (25 points) Prove that \(\operatorname{size}_{B_2}(\operatorname{MUX}_{n}) \ge 2n - o(n)\).
Hint:
When gate elimination is performed-typically after substituting some input variables with constants—it is generally required that the resulting circuit computes the same function on a reduced number of variables. In order to ensure this, try to formalize the behavior of the \(\operatorname{MUX}\) function under constant substitution to its input bits. Subsequently, prove a lower bound for a certain family of functions such that:- the function \(\operatorname{MUX}\) belongs to this family, and
- any function obtained from a member of this family by substituting constants for input bits remains within the family.