ECCC-Report TR17-129https://eccc.weizmann.ac.il/report/2017/129Comments and Revisions published for TR17-129en-usMon, 12 Feb 2018 19:01:40 +0200
Revision 8
| An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Three Rounds - An Alternative Proof |
Or Meir
https://eccc.weizmann.ac.il/report/2017/129#revision8One 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.Mon, 12 Feb 2018 19:01:40 +0200https://eccc.weizmann.ac.il/report/2017/129#revision8
Revision 7
| An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Three Rounds |
Or Meir
https://eccc.weizmann.ac.il/report/2017/129#revision7One 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.Mon, 23 Oct 2017 19:22:41 +0300https://eccc.weizmann.ac.il/report/2017/129#revision7
Revision 6
| An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Two Rounds |
Or Meir
https://eccc.weizmann.ac.il/report/2017/129#revision6One 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.Thu, 31 Aug 2017 00:17:30 +0300https://eccc.weizmann.ac.il/report/2017/129#revision6
Revision 5
| An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Three Rounds |
Or Meir
https://eccc.weizmann.ac.il/report/2017/129#revision5One 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.Wed, 30 Aug 2017 16:01:48 +0300https://eccc.weizmann.ac.il/report/2017/129#revision5
Revision 4
| Efficient Randomized Protocols for every Karchmer-Wigderson Relation with a Constant Number of Rounds |
Or Meir
https://eccc.weizmann.ac.il/report/2017/129#revision4One 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.Sun, 27 Aug 2017 22:23:54 +0300https://eccc.weizmann.ac.il/report/2017/129#revision4
Revision 3
| An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Two Rounds |
Or Meir
https://eccc.weizmann.ac.il/report/2017/129#revision3One 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.Sun, 27 Aug 2017 20:59:30 +0300https://eccc.weizmann.ac.il/report/2017/129#revision3
Revision 2
| Efficient Randomized Protocols for every Karchmer-Wigderson Relation with a Constant Number of Rounds |
Or Meir
https://eccc.weizmann.ac.il/report/2017/129#revision2One 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.Sun, 27 Aug 2017 20:56:28 +0300https://eccc.weizmann.ac.il/report/2017/129#revision2
Revision 1
| Efficient Randomized Protocols for every Karchmer-Wigderson Relation with a Constant Number of Rounds |
Or Meir
https://eccc.weizmann.ac.il/report/2017/129#revision1One 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.Sun, 27 Aug 2017 20:49:50 +0300https://eccc.weizmann.ac.il/report/2017/129#revision1
Paper TR17-129
| An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Two Rounds |
Or Meir
https://eccc.weizmann.ac.il/report/2017/129One 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.Sun, 27 Aug 2017 16:16:10 +0300https://eccc.weizmann.ac.il/report/2017/129