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)