Throughout this post, we will be considering circuits over the basis where -gates have fanin 2 and -gates are only applied to input variables. Let be a boolean function on variables and be a circuit computing . For an output gate , let and be the sub-circuits, whose outputs are inputs to . Let be the depth of circuit and be the minimum depth of a circuit computing .

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 such that . Consider the communication game between two players ( and ), where gets and gets . The goal of the players to find a coordinate such that . Let 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 we have .

Karchmer and Wigderson used the above theorem to prove that ‘monotone circuits for connectivity require super-logarithmic depth’. Let (resp. ) represent the minimum number of bits that (resp ) has to communicate. We can define type-sensitive depths of a circuit as follows. Let (resp. ) represent the AND-depth (resp. OR-depth) of .

**AND-depth** : AND-depth of an input gate is defined to be zero. AND-depth of an AND gate is max() + 1. AND-depth of an OR gate is max(). AND-depth of a circuit is the AND-depth of its output gate.

**OR-depth** is defined analogously. Let (resp. ) be the minimum AND-depth (resp. OR-depth) of a circuit computing .

Observation: For every function we have that corresponds to the AND-depth and corresponds to the OR-depth of the circuit constructed by Karchmer-Wigderson.

Open Problems :

- Can we prove explicit non-trivial lower bounds of (or ) of a given function ? 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)*