Minimum Tree-width of circuit for MAJORITY 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.
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)$.