# Type Sensitive Depth and Karchmer Wigderson Games

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)

# Random Restriction and Circuit Lower Bounds

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$ = $\{ \ |\ 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.