circuit complexity

Throughout this post, we will be considering circuits over the basis $\{\vee,\wedge,\neg\}$ where $\{\vee,\wedge\}$ -gates have fanin 2 and $\neg$ -gates are only applied to input variables. Let $f : \{0,1\}^n \rightarrow \{0,1\}$ be a boolean function on $n$ variables and $G_n$ be a circuit computing $f$ . For an output gate $g$ , let $g_l$ and $g_r$ be the sub-circuits, whose outputs are inputs to $g$ . Let $d(G_n)$ be the depth of circuit $G_n$ and $d(f)$ be the minimum depth of a circuit computing $f$ .

Karchmer and Wigderson [KW’90] showed an equivalence between circuit depth and a related problem in communication complexity. It is a simple observation that we can designate the two players as an “and-player” and an “or-player”. Let $S_0, S_1 \subseteq \{0,1\}^n$ such that $S_0 \cap S_1 = \emptyset$ . Consider the communication game between two players ( $P_{\wedge}$ and $P_{\vee}$ ), where $P_{\wedge}$ gets $x \in S_1$ and $P_{\vee}$ gets $y \in S_0$ . The goal of the players to find a coordinate $i$ such that $x_i \neq y_i$ . Let $C(S_1,S_0)$ represent the minimum number of bits they have to communicate in order for both to agree on such coordinate.

Karchmer-Wigderson Theorem : For every function $f : \{0,1\}^n \rightarrow \{0,1\}$ we have $d(f) = C(f^{-1}(1),f^{-1}(0))$ .

Karchmer and Wigderson used the above theorem to prove that ‘monotone circuits for connectivity require super-logarithmic depth’. Let $C_{\wedge}(S_1,S_0)$ (resp. $C_{\vee}(S_1,S_0)$ ) represent the minimum number of bits that $P_{\wedge}$ (resp $P_{\vee}$ ) has to communicate. We can define type-sensitive depths of a circuit as follows. Let $d_{\wedge}(G_n)$ (resp. $d_{\vee}(G_n)$ ) represent the AND-depth (resp. OR-depth) of $G_n$ .

AND-depth : AND-depth of an input gate is defined to be zero. AND-depth of an AND gate $g$ is max( $d_{\wedge}(g_l), d_{\wedge}(g_r)$ ) + 1. AND-depth of an OR gate $g$ is max( $d_{\wedge}(g_l), d_{\wedge}(g_l)$ ). AND-depth of a circuit $G_n$ is the AND-depth of its output gate.

OR-depth is defined analogously. Let $d_{\wedge}(f)$ (resp. $d_{\vee}(f)$ ) be the minimum AND-depth (resp. OR-depth) of a circuit computing $f$ .

Observation : For every function $f : \{0,1\}^n \rightarrow \{0,1\}$ we have that $C_{\wedge}(f^{-1}(1),f^{-1}(0))$ corresponds to the AND-depth and $C_{\vee}(f^{-1}(1),f^{-1}(0))$ corresponds to the OR-depth of the circuit constructed by Karchmer-Wigderson.

Open Problems :

Can we prove explicit non-trivial lower bounds of $d_{\wedge}(f)$ (or $d_{\vee}(f)$ ) of a given function $f$ ? This sort of “asymmetric” communication complexity is partially addressed in [MNSW’98].

A suitable notion of uniformity in communication games is to be defined to address such lower bounds. More on this in future posts.

References :

[KW’90] Mauricio Karchmer and Avi Wigderson : Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics, 3(2):255–265, 1990.
[MNSW’98] Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson: On Data Structures and Asymmetric Communication Complexity. J. Comput. Syst. Sci. 57(1): 37-49 (1998)

The class \aczero\ consists of all uniform families of circuits of constant depth and polynomial size, with unlimited-fanin AND and OR gates. NOT gates are allowed only at the inputs. The class \saczero\ is the semi-unbounded version of \aczero\ i.e., AND gates have constant fan-in.

The class $AC^0$ consists of all uniform families of circuits of constant depth and polynomial size, with unlimited-fanin AND and OR gates. NOT gates are allowed only at the inputs. The class $SAC^0$ is the semi-unbounded version of $AC^0$ i.e., AND gates have constant fan-in. In the class $NC^0$ both AND and OR gates have constant fan-in. The following strict hierarchy is known.

For all prime numbers $p$ , $NC^0 \subsetneq SAC^0 \subsetneq AC^0 \subsetneq AC^0[p] \subsetneq TC^0$ .

Todays post is is about the following theorem.

Theorem : $SAC^0 \subsetneq AC^0$

Proof : $AC^0$ is closed under complementation and $SAC^0$ is not.

Exercise : Prove that $SAC^0$ is not closed under complementation.

Recently I came up with an alternate proof of the above theorem using the technique of random restriction of Furst, Saxe and Sipser [FSS’81]. I think my proof can be given as a cool homework problem in introductory complexity theory course. Here it goes…..

Let $G(V,E)$ be a directed simple graph (i.e., $G$ does not have self-loops or multi-edges) with $|V|=n$ and $|E|=m$ . Let $indegree(v)$ represent the indegree of a vertex $v \in V$ . Motivated by cycle languages, we define the language $Positive Indegree$ as follows :

$Positive Indegree$ = $\{ <G(V,E)>\ |\ indegree(v)\ \geq\ 1\ \forall\ v\ \in\ V\}$ .

$G$ is represented as $(x_1,y_1),\dots,(x_m,y_m)$ where each $x_i$ and $y_i$ is in $\{1,2,\dots,n\}$ encoded as binary strings. The meaning of $(x,y)$ is that there is a directed edge from $x$ to $y$ . We may assume that circuits computing $Positive Indegree$ will have $m = O(n^2)$ binary inputs in a prespecified order.

Exercise : $Positive Indegree \in AC^0$ .

Lemma : If a CNF or a DNF computes $Positive Indegree$ , then

each term includes at least $n-1$ variables, and

there are at least $n$ terms.

Hence there is no $SAC^0$ circuit of depth two for $Positive Indegree$ .

Proof : We will prove this lemma for CNFs. The proof for DNFs is similar. Let $\mathcal{C}$ be a CNF circuit computing $Positive Indegree$ .

Assume that $\mathcal{C}$ has some term $t$ that depends on less than $n-1$ variables. Then when all inputs to $t$ are 0, $t$ outputs 0 and hence $\mathcal{C}$ outputs 0. Consider the graph $H$ consisting of a cycle on $n-1$ vertices (say $v_1,\dots,v_{n-1}$ ) and an isolated vertex $v_n$ . Note that $H \notin Positive Indegree$ . Let $H_i$ be the graph obtained by adding the edge $(v_i,v_n)$ to $H$ . Now $H_i \in Positive Indegree$ for $1 \leq i \leq n-1$ . If $t$ does not depend on all variables of the form $(v_i,v_n)$ then $\mathcal{C}$ outputs 0 for some $H_i$ , which is a contradiction.

Consider the graph $F^i$ consisting of a cycle on $n-1$ vertices (these are the vertices from $v_1,\dots,v_{n}$ except $v_i$ ) and an isolated vertex $v_i$ . $\mathcal{C}$ must output zero on $F^i$ for $1 \leq i \leq n$ . $\mathcal{C}$ outputs 0 only when one of the terms (OR gates) outputs zero. But each OR gate outputs 0 on exactly one assignment of the input variables, Hence, $\mathcal{C}$ must have at least $n$ terms.

Restriction : Let $\mathcal{C}$ be a circuit computing $Positive Indegree$ . Setting an input of $\mathcal{C}$ to 0 (resp. 1) corresponds to deleting (resp. contracting) the corresponding edge from the input graph $G$ .

Observation : If some of the inputs of $\mathcal{C}$ are restricted to 0 or 1, the resulting circuit still computes $Positive Indegree$ , albeit on a smaller graph.

Theorem : $Positive Indegree \notin SAC^0$ .

Proof : We assume that there is an $SAC^0$ circuit (say $\mathcal{C}$ of some constant depth $d$ ) computing $Positive Indegree$ and derive a contradiction. Using the random restriction technique of [FSS’81] we squash $\mathcal{C}$ down to depth $d-1$ while still computing $Positive Indegree$ on many variables. This squashing still preserves the constant fanin of AND gates. We repeat this method $d-2$ times to obtain an $SAC^0$ circuit of depth 2 with constant AND fanin, which contradicts the previous lemma.

Corollary : $SAC^0 \subsetneq AC^0$ .

References :

[FSS’81] Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. In FOCS, pages 260–270, 1981.

My Brain is Open

Computational Complexity, Polyhedral Combinatorics, Algorithms and Graph Theory

Type Sensitive Depth and Karchmer Wigderson Games

Random Restriction and Circuit Lower Bounds

Share this:

Share this: