12
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Why is this not trivial for any $\mathrm{NC}^1$ language? As far as I can see, formulas (i.e., trees) have tree-width $1$, or am I missing something? $\endgroup$ – Emil Jeřábek supports Monica Oct 10 '14 at 13:49
  • 5
    $\begingroup$ I think OP identifies all leaves of the formula tree that correspond to the same variable, which creates cycles. $\endgroup$ – Sasho Nikolov Oct 10 '14 at 14:35
  • 1
    $\begingroup$ A circuit for majority can be implemented in treewidth O(log n). The circuit just simulates an online algorithm that reads one input bit at a time and adds 1 to a number with O(log n) bits if and only if the input is 1. Note that the depth of the circuit is O(n). See Fig 1 of (arxiv.org/pdf/1404.5565v1.pdf). A circuit of small depth has not necessarily small treewidth because as Sasho Nikolov pointed out you need to identify nodes corresponding to the same input variable. $\endgroup$ – Mateus de Oliveira Oliveira Oct 10 '14 at 15:41
  • $\begingroup$ @MateusdeOliveiraOliveira The construction you point out is nice and simple and is almost what I need. What I really need is a construction that works in bounded tree width (or some indication why that is not possible). I will wait for a couple of days to see if there is any other answer - otherwise (if you convert your comment to an answer) I will approve it. $\endgroup$ – SamiD Oct 10 '14 at 21:15
  • $\begingroup$ @SamiD I expanded this comment into an answer. I hadn't post as an answer before because it is only half of what you asked. $\endgroup$ – Mateus de Oliveira Oliveira Oct 11 '14 at 20:25
7
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ As a side remark, doing the same circuit but as a binary tree (with the output at the root) rather than a path gives a circuit with treewidth O(log n) and depth O(log n) $\endgroup$ – daniello Oct 15 '14 at 8:57
  • 1
    $\begingroup$ It seems that a direct translation into trees would give depth O((log n)^2) since we would need depth O(log n) for each adder. But its true that the treewidth would be O(log n). $\endgroup$ – Mateus de Oliveira Oliveira Oct 16 '14 at 13:34
  • $\begingroup$ Of course you are right, thanks! It seems that if the additions are implemented as DNFs then we get treewidth and depth O(log n), but size $O(n^3)$. $\endgroup$ – daniello Oct 16 '14 at 14:04
  • $\begingroup$ the thing with representing the adder as DNFs is that it can potentially increase the treewidth, since now each variable will be shared with (at first glance polynomially) many clauses. Your suggestion to reduce the depth to O(log n) would work if you can show that addition of two numbers with O(log n) bits can be done in constant depth and logarithmic treewidth. $\endgroup$ – Mateus de Oliveira Oliveira Oct 18 '14 at 16:41
  • $\begingroup$ Well - for any Boolean function on $a$ input bits and $b$ output bits the DNF has depth $2$, size $2^a + a + b$, and treewidth $\leq a+b$ since deleting input + output gates leaves an independent set... $\endgroup$ – daniello Oct 20 '14 at 6:49
5
$\begingroup$

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...]

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.