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)

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s