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 #8 to TR17-129 | 12th February 2018 19:01

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

RSS-Feed




Revision #8
Authors: Or Meir
Accepted on: 12th February 2018 19:01
Downloads: 769
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
Downloads: 1009
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
Downloads: 734
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: 877
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: 724
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: 1723
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: 792
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: 730
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: 1040
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