Disclaimer: I admit that the question is not very clear. I think it cannot be helped because the question is very open-ended.

First of all, I present the interested type of circuits. We only consider this structure of Boolean / Arithmetic circuits: a DAG consisting of multiple inputs, 1 output and multiple gates. Each gate has fan-in $\le 2$ and unlimited fan-out (in principle). Also, we only consider Boolean gates (NOT, AND, OR), and Arithmetic gates (ADD, MULTIPLY).

Let $f: \mathbb{B}^n \rightarrow \mathbb{B}$ be a Boolean function and $G(f)$ be the set of its corresponding Boolean circuits with size poly$(n)$. For each circuit $C \in G(f)$, we can transform it into $C' \in G(f)$ only consisting of NOT and AND gates, by using De Morgan's laws.

Then, we place weights on every edge of $C'$ as follows (called Rule 0): place indeterminate $X$ on every input edge of AND gates, and place $1$ on every input edge of NOT gates. Now we can construct $f_0(C) \in \mathbb{Z}[X]$ as follows:

  1. At each input node of $C'$, assign $1 \in \mathbb{Z}[X]$ as its value.
  2. At each of other nodes of $C'$, say node $u$, compute its value $\in \mathbb{Z}[X]$: $$\text{val}(u) = \sum_{\text{edge } (v,u)} \text{val}(v)\cdot\text{weight}(v, u)$$
  3. $f_0(C)$ is the value of the output node of $C'$.

With $f_0(C)$, we have an alternative definition of circuit depth: the depth of $C$ is $\deg f_0(C)$. Therefore, in a way, the best circuits to compute $f$ are the minimum circuits in $G(f)$ w.r.t $\deg f_0(\cdot)$.

In a similar manner, we can change the weighting rule into Rule 1 to get $f_1(C)$. Particularly, Rule 1 is as follows: place indeterminate $X$ on only one of the input edges of each AND gate, and place $1$ on each of other edges. Now $f_1(C)$ is the minimum-degree value of the output node of $C'$, out of all weighting scenarios. So we have a variant definition of circuit depth: the depth of $C$ is $\deg f_1(C)$.

Naturally, the research question has risen: what is the best circuits to compute $f$ w.r.t $\deg f_1(\cdot)$. In other words, given $f$, what are the minimum circuits in $G(f)$ w.r.t $\deg f_1(\cdot)$?

Lastly, I quickly present why there is an Arithmetic aspect of all this. One can see easily that we can transform $C'$ into Arithmetic poly$(n)$-size circuits $D_0, D_1$, both of which have 1 input (indeterminate $X$), 1 output, and $f_0(C), f_1(C)$ as their outputs, respectively. In the transformations, the input nodes of $C'$ become the constant nodes of 1.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.