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)


Logspace vs Polynomial time

One of the primary goals of complexity theory is separating complexity classes, a.k.a proving lower bounds. Embarrassingly we have only a handful of unconditional separation results. Separating P from NP is of course the mother of all such goals. Anybody who understands the philosophical underpinnings of the P vs NP problem would love to LIVE to see its resolution. Towards resolving this, we made some (“anti”)-progress (Eg : Relativization, Natural proofs, Algebrization) and have a new geometric complexity theory approach which relies on an Extended-Extended-Extended-Extended-Riemann-Hypothesis !! For more information about the history and status of P vs NP problem read Sipser’s paper [Sipser’92], Allender’s status report [Allender’09] or Fortnow’s article [Fortnow’09].

Today’s post is about the Logspace (L) vs Polynomial time (P) problem, which (in my opinion) is right next to the P vs NP problem in its theoretical importance. I guess many researchers believe that L \neq P. Did we make any progress/anti-progress towards resolving the L \neq P conjecture ?  Here are two attempts both based on branching programs and appeared in MFCS with a gap of 20 years !!

1) A conjecture by Barrington and McKenzie (BM’89): The problem GEN is defined as follows :

GEN : Given an n \times n table filled with entries from \{1,2,\dots,n\}, which we interpret as the multiplication table of an n-element groupoid, and a subset S of \{1,2,\dots,n\} which includes element 1, determine whether the subgroupoid <S>, defined as the closure of S under the groupoid product, includes element n.

Barrington-McKenzie Conjecture : For each n > 1, a branching program in which each node can only evaluate a binary product within an n-element groupoid, branching n ways according to the n possible outcomes, must have at least 2^{n-2} nodes to solve all n \times n GEN instances with singleton starting set S.

The problem GEN is known to be P-complete [JL’76]. Barrington-McKenzie Conjecture would imply that GEN \notin DSPACE({{\log}^k}n) for any k. In particular, it would imply that L \neq P. I don’t know if there is any partial progress towards resolving this conjecture.

2) Thrifty Hypothesis : This is a recent approach by Braverman et. al [BCMSW’09] towards proving a stronger theorem L \neq LogDCFL. Stephen Cook presented this approach at Valiant’s 60th birthday celebration and Barriers Workshop. He also announced a $100 prize for solving an intermediate open problem mentioned in his slides.

Tree Evaluation Problem (TEP): The input to the problem is a rooted, balanced d-ary tree of height h, whose internal nodes are labeled with d-ary functions on [k] = \{1, . . . , k\}, and whose leaves are labeled with elements of [k]. Each node obtains a value in [k] equal to its d-ary function applied to the values of its d children. The output is the value of the root.

In their paper they show that TEP \in LogDCFL and conjecture that TEP \notin L. They introduce Thrifty Branching Programs and prove that TEP can be solved by a thrifty branching program. A proof of the following conjecture implies that L \neq LogDCFL. For more details, read this paper.
Thrifty Hypothesis : Thrifty Branching Programs are optimal among deterministic branching programs solving TEP.

Open Problems :

  • My knowledge about the history of L vs P problem is limited.  Are there other approaches/attempts in the last four decades to separate L from P ?
  • An intermediate open problem is mentioned in the last slide of these slides. The authors announced $100 prize for the first correct proof. Read their paper for more open problems.

References :

  • [BM’89] David A. Mix Barrington, Pierre McKenzie: Oracle Branching Programs and Logspace versus P. MFCS 1989: 370-379
  • [BCMSW’09] Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr: Branching Programs for Tree Evaluation. MFCS 2009: 175-186
  • [Sipser’92] Michael Sipser: The History and Status of the P versus NP Question STOC 1992: 603-618
  • [Allender’09] Eric Allender: A Status Report on the P Versus NP Question. Advances in Computers 77: 117-147 (2009) [pdf]
  • [Fortnow’09] Lance Fortnow: The status of the P versus NP problem. Commun. ACM 52(9): 78-86 (2009) [pdf]
  • [JL’76] Neil D. Jones, William T. Laaser: Complete Problems for Deterministic Polynomial Time. Theor. Comput. Sci. 3(1): 105-117 (1976)

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.