# 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)

# 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.