Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #8 to TR17-129 | 12th February 2018 19:01

#### An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Three Rounds - An Alternative Proof

Revision #8
Authors: Or Meir
Accepted on: 12th February 2018 19:01
Keywords:

Abstract:

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.

Changes to previous version:

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

Revision #7 to TR17-129 | 23rd October 2017 19:22

#### An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Three Rounds

Revision #7
Authors: Or Meir
Accepted on: 23rd October 2017 19:22
Keywords:

Abstract:

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.

Changes to previous version:

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

Revision #6 to TR17-129 | 31st August 2017 00:17

#### An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Two Rounds

Revision #6
Authors: Or Meir
Accepted on: 31st August 2017 00:17
Keywords:

Abstract:

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.

Revision #5 to TR17-129 | 30th August 2017 16:01

#### An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Three Rounds

Revision #5
Authors: Or Meir
Accepted on: 30th August 2017 16:01
Keywords:

Abstract:

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.

Revision #4 to TR17-129 | 27th August 2017 22:23

#### Efficient Randomized Protocols for every Karchmer-Wigderson Relation with a Constant Number of Rounds

Revision #4
Authors: Or Meir
Accepted on: 27th August 2017 22:23
Keywords:

Abstract:

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.

Changes to previous version:

Small correction to Theorem 4.

Revision #3 to TR17-129 | 27th August 2017 20:59

#### An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Two Rounds

Revision #3
Authors: Or Meir
Accepted on: 27th August 2017 20:59
Keywords:

Abstract:

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.

Revision #2 to TR17-129 | 27th August 2017 20:56

#### Efficient Randomized Protocols for every Karchmer-Wigderson Relation with a Constant Number of Rounds

Revision #2
Authors: Or Meir
Accepted on: 27th August 2017 20:56
Keywords:

Abstract:

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.

Revision #1 to TR17-129 | 27th August 2017 20:49

#### Efficient Randomized Protocols for every Karchmer-Wigderson Relation with a Constant Number of Rounds

Revision #1
Authors: Or Meir
Accepted on: 27th August 2017 20:49
Keywords:

Abstract:

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.

### Paper:

TR17-129 | 27th August 2017 15:36

#### An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Two Rounds

TR17-129
Authors: Or Meir
Publication: 27th August 2017 16:16
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint