Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

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

RSS-Feed




Revision #6
Authors: Or Meir
Accepted on: 31st August 2017 00:17
Downloads: 36
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
Downloads: 18
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
Downloads: 50
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
Downloads: 24
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
Downloads: 18
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
Downloads: 12
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
Downloads: 88
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