Minimum Tree-width of circuit for MAJORITY

Question

What is the minimum tree-width of a circuit over $\{\wedge,\vee,\neg\}$ for computing MAJ?

Here MAJ $:\{0,1\}^n \rightarrow \{0,1\}$ outputs 1 iff at least half of its inputs are $1$.

I care only about the size of the circuit (ought to be polynomial) and that an input should be read only once though the fan-out of an input gate can be arbitrary (this crucially affects the tree-width of the circuit - the branching programs obtained from Barrington's theorem from the MAJ $\in$ $\mathsf{NC}^1$, interpreted as skew circuits, do not help). And of course the tree-width is the most crucial thing. I do not care about the depth or any other parameter.

Some of the common circuits for MAJ include:

• Wallace tree circuits (e.g.Theorem 8.9 here) which use the 3-to-2 trick to place MAJ in $\mathsf{NC}^1$?
• Valiant's monotone $\mathsf{NC}^1$ circuits for MAJ (e.g. Theorem 4 here)
• $\log^{O(1)}{n}$ depth sorting network such as Batcher sort
• AKS sorting network

Do any of them have bounded or even polylogarithmic tree-width?

Or in fact,

Are there reasons to believe that there are no bounded tree-width circuits for MAJ?

Notice that every function computed by a bounded tree-width circuit can be computed by an $\mathsf{NC}^1$ circuit even when there is no read-once stipulation via JansenSarma. Thus the implausibility of such a circuit family would indicate that this bound can be tightened further in the case of read-once circuits.

Answer 1

Answering half of Samir's question.

Let $G=(V,E)$ be a DAG and $V_1,V_2\subseteq V$ be two subsets of vertices of $G$. We denote by $E(V_1,V_2)$ the set of all edges in $G$ with one endpoint in $V_1$ and other endpoint in $V_2$. If $\omega = (v_1,...,v_n)$ is a total ordering of the vertices of $G$ then we let $$\mathbf{ow}(G,\omega) = \max_{i}\; |E(\{v_1,...,v_i\},\{v_{i+1},...,v_n\}|$$ denote the width of $\omega$. The online width of $G$ is defined as $$\mathbf{ow}(G) = \min_{\omega}\; \mathbf{ow}(G,\omega),$$ where the minimum is taken over all topological orderings of the vertices of $G$. Note that the traditional notion of cutwidth of $G$, $\mathbf{cw}(G)$ is defined analogously, except that the minimum is taken over all possible orderings of $G$, irrespectively of whether the ordering is topological or not. We have the following sequence of inequalities: $$\mathbf{tw}(G) \leq \mathbf{pw}(G) \leq \mathbf{cw}(G)\leq \mathbf{ow}(G),$$ where $\mathbf{pw}(G)$ and $\mathbf{tw}(G)$ are respectively the pathwidth and the treewidth of $G$.

We claim that MAJORITY of $n$ bits can be computed in online-width $O(\log n)$, and therefore in treewidth $O(\log n)$. The circuit simulates an online algorithm that reads one input bit $b$ at a time and adds $b$ to a counter with $O(\log n)$ bits if and only if $b=1$. At the beggining, the counter is initialized to $0$. At the end the circuit accepts if and only if the value of the counter is greater than n/2. It is easy to see that the gates of a circuit ADD that adds one to the counter register can be topologically-ordered in such a way that it has constant online width, since this circuits just need to implement an carry on operation. The total circuit is a sequence of circuits $C=(ADD_1,ADD_2,...,ADD_n,COMP)$ where the output of $ADD_i$ is plugged to the input of $ADD_{i+1}$, and the output of $ADD_n$ is plugged to the input of COMP. Now if we topologically-order the total circuit $C$ in such a way that all gates of $ADD_i$ appear before the gates of $ADD_{i+1}$ and all gates of $ADD_n$ appear before the gates of COMP, then this topological order has online width $O(\log n)$. This construction is illustrated in Figure 1 of a paper of mine to show that probability amplification can be done in logarithmic online width.

Obs: The depth of the circuit C is $O(n)$.

Answer 2

Answering the other half of the question - here is a proof sketch for a $c \cdot \log n$ lower bound for the treewidth for some constant $c$. The bound is independent of the size or any other aspect of the circuit. In the rest of the argument $C$ is the circuit, $t$ is the treewidth of $C$ and $n$ is the number of input gates.

The first step is to use the balanced separator lemma for graphs of bounded treewidth. The gates (including the input gates) of the circuit may be partitioned into three parts $L$, $R$ and $S$, such that $|S| \leq t+1$ and both $L$ and $R$ contain at least $n/3-|S|$ input gates, and there are no arcs (wires) between $L$ and $R$.

In the rest of the proof the only property of the circuit we will use is this partitioning - so the proof actually gives a lower bound on the size of a balanced separator $S$ as above.

Having $(L,S,R)$ at hand we construct a circuit $C'$ from $C$ as follows: for each gate $g$ in $S$ make two more gates $g_L$ and $g_R$, and make $g_L$ and $g_R$ feed into $g$. For all wires leading into $g$ from $L$ make them go into $g_L$ instead. For all wires leading into $g$ from $R$ make them go into $g_R$ instead. Let $$S' = \{g, g_L, g_R : g \in S\}.$$

For each of the $2^{|S'|}$ assingments to $S'$ make a circuit that outputs 1 if (a) the assignment to the input gates makes $C'$ output true and (b) the assignment to the input gates sets all the gates of $S'$ as guessed. Call these circuits $C_1$, $C_2$, $C_3 \ldots C_x$ for $x \leq 8^t$. Note that the circuit $C_i$ naturally breaks up into two subcircuits $C_i^L$ and $C_i^R$ such that $C_i^L$ only depends on the input gates of $L \cup S'$, $C_i^R$ only depends on the input gates of $R \cup S'$, and for any assignment to the input gates we have that $C_i = C_i^L \wedge C_i^R$.

Since every assignment to the input gates is consistent with some guess for what happens in $S'$ we have that $C' = C_1 \vee C_2 \vee C_3 \ldots \vee C_x$. Thus we have re-written the circuit $C$ as an OR (of fanin $8^t$) of AND's (of fanin $2$) where the AND gate number $i$ is being fed the output of $C_i^L$ and $C_i^R$ respectively.

Let $Z$ be the set of topmost AND-gates. We will first prove that $2^{|Z|} \geq n/3-|S|$. This gives a simple $\log \log n$ lower bound on $t$. We will then prove a better bound.

---

Suppose $2^{|Z|} < n/3-|S|$, and assume w.l.o.g. that $L$ contains fewer input gates than $R$. Then both $L$ and $R$ contain at least $n/3-|S|$ input gates. By the pigeon hole principle there are two different numbers $i$ and $j$ such that there are two different assignments to the input gates of $L$, one that sets $i$ gates to true, one that sets $j$, such that the circuits $C_1^L$, $C_2^L \ldots C_x^L$ all output the same thing. But there exists an assignment to the input gates in $R$ such that MAJORITY outputs FALSE if $i$ gates in $L$ are set to true, and MAJORITY outputs TRUE if $j$ gates in $L$ are set to true. This is a contradiction, and so $2^{|Z|} \geq n/3-|S|$ implying that treewidth is at least $\log \log n$.

---

We now show a better bound: $|Z| \geq n/3-|S|$. Assume w.l.o.g. that $L$ contains fewer input gates than $R$. Then both L and R contain at least $n/3-|S|$ input gates. Consider the "all false" assignment to $L$. Let $r$ be the smallest number of input gates of $R$ that has to be set to true such that MAJ outputs TRUE, given that all of $L$ is set to false.

Since setting $L$ to all false and exactly $r$ input gates of $R$ to true makes MAJORITY output $1$ there has to be some $i$ such that $C_i^L$ outputs TRUE, w.l.o.g. this is $C_1^L$. All assignments to $R$ with less than $r$ true input gates must set $C_1^R$ to false. Since setting $1$ input gate of $L$ to true and $r-1$ input gates of $R$ to true makes MAJORITY output $1$, setting $1$ gate of $L$ to true must make at least one $C_i^L$ outpur true for $i \neq 1$. w.l.o.g we can assume $i=2$. Then all assignments to $R$ that set at most $r-2$ input gates to true must set $C_2^R$ to false, and so on - we may repeat this argument $r$ times. But this means that $|Z| \geq r \geq n/3-|S|$, giving a $c \cdot \log n$ lower bound for $t$.

[I am aware that this sketch gets a bit hand-wavy at places, ask away if something is unclear...]