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.

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.