Month: November 2010

by

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)

 

by

Balanced ST-Connectivity

Today’s post is about a new open problem arising from my recent paper  (available on ECCC). The problem is as follows :

Let G(V,E) be a directed graph. Let G'(V,E') be the underlying undirected graph of G. Let P be a path in G'. Let e = (u,v) be an edge along the path P. Edge e is called neutral edge if both (u,v) and (v,u) are in E. Edge e is called forward edge if (u,v) \in E and (v,u) \notin E. Edge e is called backward edge if (u,v) \notin E and (v,u) \in E.

A path (say P) from s \in V to t \in V in G'(V,E') is called balanced if the number of forward edges along P is equal to the number of backward edges along P. A balanced path might have any number of neutral edges. By definition, if there is a balanced path from s to t then there is a balanced path from t to s. The path P may not be a simple path. We are concerned with balanced paths of length at most n.

Balanced ST-Connectivity : Given a directed graph G(V,E) and two distinguished nodes s and t, decide if there is balanced path (of length at most n) between s and t.

In my paper, I proved that SGSLOGCFL, a generalization of Balanced ST-Connectivity, is contained in DSPACE(lognloglogn). Details about SGSLOGCFL are in my paper.

Theorem 1 : SGSLOGCFL is in DSPACE(lognloglogn).

Open Problem : Is SGSLOGCFL \in L ?

Cash Prize : I will offer $100 for a proof of SGSLOGCFL \in L. I have spent enough sleepless nights trying to prove it. In fact, an alternate proof of Theorem 1 (or even any upper bound better than O({\log}^2n)) using zig-zag graph product seems to be a challenging task.

Usually people offer cash prizes for a mathematical problem when they are convinced that :

  • it is a hard problem.
  • it is an important problem worth advertising.
  • the solution would be beautiful, requires new techniques and sheds new light on our understanding of related problems.

My reason is “All the above”. Have Fun solving it !!

A cute puzzle : In Balanced ST-Connectivity we are only looking for paths of length at most n. There are directed graphs where the only balanced st-path is super-linear. The example in the following figure shows an instance of Balanced ST-Connectivity where the only balanced path between s and t is of length \Theta(n^2). The directed simple path from s to t is of length n/2. There is a cycle of length n/2 at the vertex v. All the edges (except (v,u)) on this cycle are undirected. The balanced path from s to t is obtained by traversing from s to v, traversing the cycle clockwise for n/2 times and then traversing from v to t.

Puzzle : Are there directed graphs where every balanced st-path is of super-polynomial size ?

Update : The above puzzle is now solved.

Open Problems

  • Is SGSLOGCFL \in L ?
  • Are there directed graphs where every balanced st-path is of super-polynomial size ? (solved)
  • More open problems are mentioned in my paper.