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.

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.

Small correction to Theorem 4.

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.