0
$\begingroup$

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.

$\endgroup$

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.