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