One of the important challenges in circuit complexity is proving strong
lower bounds for constant-depth circuits. One possible approach to
this problem is to use the framework of Karchmer-Wigderson relations: Karchmer and Wigderson (SIDMA 3(2), 1990) observed that for every Boolean function $f$ there is a corresponding communication problem $\mathrm{KW}_f$, called the Karchmer-Wigderson relation of f, whose deterministic communication complexity is tightly related to the depth complexity of $f$. In particular, if we could prove that every deterministic constant-round protocol for $\mathrm{KW}_f$ must transmit at least $c$ bits, then this would imply a lower bound of $2^{\Omega(c)}$ on the size of constant-depth circuits computing $f$.

Jowhari, Saglam, and Tardos (PODS 2011) showed that there is a randomized three-round protocol that solves every Karchmer-Wigderson relation $\mathrm{KW}_f$ by transmitting only $O(\log n)$ bits. This means that if we wish to use Karchmer-Wigderson relations in order to prove super-polynomial lower bounds for constant-depth circuits, then we cannot use techniques that work against randomized protocols.

The protocols of Jowhari et. al. are based on a result from the sketching literature. In this note, we replace this tool with a simple protocol that is based on the Hamming code. This results in protocols that require no background in sketching to understand. The aforementioned simple protocol is a deterministic two-round protocol that solves a special case of Karchmer-Wigderson relations, and may be of independent interest.

Abstract Clarification: Following an earlier revision of this work, it has been brought to our attention that a very similar protocol to ours has already appeared in the M.Sc. thesis of Mert S?glam.

Now gives credit to Saglam's M.Sc. thesis.

One of the important challenges in circuit complexity is proving strong
lower bounds for constant-depth circuits. One possible approach to
this problem is to use the framework of Karchmer-Wigderson relations: Karchmer and Wigderson (SIDMA 3(2), 1990) observed that for every Boolean function $f$ there is a corresponding communication problem $KW_f$,
called the Karchmer-Wigderson relation of $f$, whose deterministic communication complexity is tightly related to the depth complexity of $f$. In particular, if we could prove that every deterministic constant-round protocol for $KW_f$ must transmit at least $c$
bits, then this would imply a lower bound of $2^\Omega(c)$ on the size of constant-depth circuits computing $f$.

Jowhari, Saglam, and Tardos (PODS 2011) showed that there is a randomized three-round protocol that solves every Karchmer-Wigderson relation $KW_f$ by transmitting only $O(\log n)$ bits. This means that if we wish to use Karchmer-Wigderson relations in order to prove super-polynomial lower bounds for constant-depth circuits, then we cannot use techniques that work against randomized protocols.

The protocols of Jowhari et. al. are based on a result from the sketching literature. In this note, we replace this tool with a simple protocol that is based on the Hamming code. This results in protocols that require no background in sketching to understand. The aforementioned simple protocol is a deterministic two-round protocol that solves a special case of Karchmer-Wigderson relations, and may be of independent interest.

Now gives proper credit to Hastad for the efficient randomized protocol that solves KW relations with an unbounded number of rounds.

One of the important challenges in circuit complexity is proving strong
lower bounds for constant-depth circuits. One possible approach to
this problem is to use the framework of Karchmer-Wigderson relations:
Karchmer and Wigderson (SIDMA 3(2), 1990) observed that for every Boolean
function $f$ there is a corresponding communication problem ${KW}_{f}$,
called the Karchmer-Wigderson relation of $f$, whose deterministic
communication complexity is tightly related to the depth complexity
of $f$. In particular, if we could prove that every deterministic
constant-round protocol for ${KW}_{f}$ must transmit at least $c$
bits, then this would imply a lower bound of $2^{\Omega(c)}$ on
the size of constant-depth circuits computing $f$.

Jowhari, Saglam, and Tardos (PODS 2011) showed that there is a randomized three-round protocol that solves every Karchmer-Wigderson relation ${KW}_{f}$ by transmitting only $O(\log n)$ bits. This means that if we wish to use Karchmer-Wigderson relations in order to prove super-polynomial lower bounds for constant-depth circuits, then we cannot use techniques that work against randomized protocols.

The protocols of Jowhari et. al. are based on a result from the sketching literature. In this note, we replace this tool with a simple protocol that is based on the Hamming code. This results in protocols that require no background in sketching to understand. The aforementioned simple protocol is a deterministic two-round protocol that solves a special case of Karchmer-Wigderson relations, and may be of independent interest.

One of the important challenges in circuit complexity is proving strong
lower bounds for constant-depth circuits. One possible approach to
this problem is to use the framework of Karchmer-Wigderson relations:
Karchmer and Wigderson (SIDMA 3(2), 1990) observed that for every Boolean
function $f$ there is a corresponding communication problem ${KW}_{f}$,
called the Karchmer-Wigderson relation of $f$, whose deterministic
communication complexity is tightly related to the depth complexity
of $f$. In particular, if we could prove that every deterministic
constant-round protocol for ${KW}_{f}$ must transmit at least $c$
bits, then this would imply a lower bound of $2^{\Omega(c)}$ on
the size of constant-depth circuits computing $f$.

Jowhari, S\u{a}glam, and Tardos (PODS 2011) showed that there is a randomized three-round protocol that solves every Karchmer-Wigderson relation ${KW}_{f}$ by transmitting only $O(\log n)$ bits. This means that if we wish to use Karchmer-Wigderson relations in order to prove super-polynomial lower bounds for constant-depth circuits, then we cannot use techniques that work against randomized protocols.

The protocols of Jowhari et. al. are based on a result from the sketching literature. In this note, we replace this tool with a simple protocol that is based on the Hamming code. This results in protocols that require no background in sketching to understand. The aforementioned simple protocol is a deterministic two-round protocol that solves a special case of Karchmer-Wigderson relations, and may be of independent interest.

One of the important challenges in circuit complexity is proving strong
lower bounds for constant-depth circuits. One possible approach to
this problem is to use the framework of Karchmer-Wigderson relations:
Karchmer and Wigderson (SIDMA 3(2), 1990) observed that for every Boolean
function $f$ there is a corresponding communication problem ${KW}_{f}$,
called the Karchmer-Wigderson relation of $f$, whose deterministic
communication complexity is tightly related to the depth complexity
of $f$. In particular, if we could prove that every deterministic
constant-round protocol for ${KW}_{f}$ must transmit at least $c$
bits, then this would imply a lower bound of $2^{\Omega(c)}$ on
the size of constant-depth circuits computing $f$.

Abstract Jowhari, Saglam, and Tardos (PODS 2011) showed that there is a randomized two-round protocol that solve every Karchmer-Wigderson relation ${KW}_{f}$ by transmitting only $O(\log^{2}n)$ bits. Furthermore, there is such a randomized four-round protocol that uses only $O(\log n)$. This means that if we wish to use Karchmer-Wigderson relations in order to prove exponential lower bounds for constant-depth circuits, then we cannot use techniques that work against randomized protocols.

The protocols of Jowhari et. al. are based on a result from the sketching literature. In this note, we replace this tool with a simple protocol that is based on the Hamming code. This results in protocols that require no background in sketching to understand. The aforementioned simple protocol is a deterministic two-round protocol that solves a special case of Karchmer-Wigderson relations, and may be of independent interest.

Small correction to Theorem 4.

One of the important challenges in circuit complexity is proving strong
lower bounds for constant-depth circuits. One possible approach to
this problem is to use the framework of Karchmer-Wigderson relations:
Karchmer and Wigderson (SIDMA 3(2), 1990) observed that for every Boolean
function $f$ there is a corresponding communication problem ${KW}_{f}$,
called the Karchmer-Wigderson relation of $f$, whose deterministic
communication complexity is tightly related to the depth complexity
of $f$. In particular, if we could prove that every deterministic
constant-round protocol for ${KW}_{f}$ must transmit at least $c$
bits, then this would imply a lower bound of $2^{\Omega(c)}$ on
the size of constant-depth circuits computing $f$.

Jowhari, Saglam, and Tardos (PODS 2011) showed that there is a randomized two-round protocol that solve every Karchmer-Wigderson relation ${KW}_{f}$ by transmitting only $O(\log^{2}n)$ bits. Furthermore, there is such a randomized four-round protocol that uses only $O(\log n)$. This means that if we wish to use Karchmer-Wigderson relations in order to prove exponential lower bounds for constant-depth circuits, then we cannot use techniques that work against randomized protocols.

The protocols of Jowhari et. al. are based on a result from the sketching literature. In this note, we replace this tool with a simple protocol that is based on the Hamming code. This results in protocols that require no background in sketching to understand. The aforementioned simple protocol is a deterministic two-round protocol that solves a special case of Karchmer-Wigderson relations, and may be of indepedent interest.

One of the important challenges in circuit complexity is proving strong
lower bounds for constant-depth circuits. One possible approach to
this problem is to use the framework of Karchmer-Wigderson relations:
Karchmer and Wigderson (SIDMA 3(2), 1990) observed that for every Boolean
function $f$ there is a corresponding communication problem $\mathrm{KW}_{f}$,
called the Karchmer-Wigderson relation of $f$, whose deterministic
communication complexity is tightly related to the depth complexity
of $f$. In particular, if we could prove that every deterministic
constant-round protocol for $\mathrm{KW}_{f}$ must transmit at least $c$
bits, then this would imply a lower bound of $2^{\Omega(c)}$ on
the size of constant-depth circuits computing $f$.

Abstract Jowhari, Saglam, and Tardos (PODS 2011) showed that there is a randomized two-round protocol that solve every Karchmer-Wigderson relation $\mathrm{KW}_{f}$ by transmitting only $O(\log^{2}n)$ bits. Furthermore, there is such a randomized four-round protocol that uses only $O(\log n)$. This means that if we wish to use Karchmer-Wigderson relations in order to prove exponential lower bounds for constant-depth circuits, then we cannot use techniques that work against randomized protocols.

Abstract The protocols of Jowhari et. al. are based on a result from the sketching literature. In this note, we replace this tool with a simple protocol that is based on the Hamming code. This results in protocols that require no background in sketching to understand. The aforementioned simple protocol is a deterministic two-round protocol that solves a special case of Karchmer-Wigderson relations, and may be of indepedent interest.

One of the important challenges in circuit complexity is proving strong
lower bounds for constant-depth circuits. One possible approach to
this problem is to use the framework of Karchmer-Wigderson relations:
Karchmer and Wigderson (SIDMA 3(2), 1990) observed that for every Boolean
function $f$ there is a corresponding communication problem $\mathrm{KW}_{f}$,
called the Karchmer-Wigderson relation of $f$, whose deterministic
communication complexity is tightly related to the depth complexity
of $f$. In particular, if we could prove that every deterministic
constant-round protocol for $\mathrm{KW}_{f}$ must transmit at least $c$
bits, then this would imply a lower bound of $2^{\Omega(c)}$ on
the size of constant-depth circuits computing $f$.

Jowhari, Saglam, and Tardos (PODS 2011) showed that there is a randomized two-round protocol that solve every Karchmer-Wigderson relation $\mathrm{KW}_{f}$ by transmitting only $O(\log^{2}n)$ bits. Furthermore, there is such a randomized four-round protocol that uses only $O(\log n)$. This means that if we wish to use Karchmer-Wigderson relations in order to prove exponential lower bounds for constant-depth circuits, then we cannot use techniques that work against randomized protocols.

The protocols of Jowhari et. al. are based on a result from the sketching literature. In this note, we replace this tool with a simple protocol that is based on the Hamming code. This results in protocols that require no background in sketching to understand. The aforementioned simple protocol is a deterministic two-round protocol that solves a special case of Karchmer-Wigderson relations, and may be of indepedent interest.

One of the important challenges in circuit complexity is proving strong
lower bounds for constant-depth circuits. One possible approach to
this problem is to use the framework of Karchmer-Wigderson relations:
Karchmer and Wigderson (SIDMA 3(2), 1990) observed that for every Boolean
function $f$ there is a corresponding communication problem $\mathrm{KW}_{f}$,
called the Karchmer-Wigderson relation of $f$, whose deterministic
communication complexity is tightly related to the depth complexity
of $f$. In particular, if we could prove that every deterministic
constant-round protocol for $\mathrm{KW}_{f}$ must transmit at least $c$
bits, then this would imply a lower bound of $2^{\Omega(c)}$ on
the size of constant-depth circuits computing $f$.

In this work, we observe that there is a randomized two-round
protocol that solves every Karchmer-Wigderson relation $\mathrm{KW}_{f}$
by transmitting only $O(\log^{2}n)$ bits. This means that if we
wish to use Karchmer-Wigderson relations in order to prove exponential
lower bounds for constant-depth circuits, then we cannot use techniques
that work against randomized protocols.