ECCC-Report TR20-116https://eccc.weizmann.ac.il/report/2020/116Comments and Revisions published for TR20-116en-usWed, 19 May 2021 06:55:47 +0300
Revision 2
| Toward better depth lower bounds: the XOR-KRW conjecture |
Alexander Smal,
Ivan Mihajlin
https://eccc.weizmann.ac.il/report/2020/116#revision2In this paper, we propose a new conjecture, the XOR-KRW conjecture, which is a relaxation of the Karchmer-Raz-Wigderson conjecture [KRW95]. This relaxation is still strong enough to imply $\mathbf{P} \not\subseteq \mathbf{NC}^1$ if proven. We also present a weaker version of this conjecture that might be used for breaking $n^3$ lower bound for De~Morgan formulas. Our study of this conjecture allows us to partially answer an open question stated in [GMWW17] regarding the composition of the universal relation with a function. To be more precise, we prove that there exists a function $g$ such that the composition of the universal relation with $g$ is significantly harder than just a universal relation. The fact that we can only prove the existence of $g$ is an inherent feature of our approach.
The paper's main technical contribution is a method of converting lower bounds for multiplexer-type relations into lower bounds against functions. In order to do this, we develop techniques to lower bound communication complexity using reductions from non-deterministic communication complexity and non-classical models: half-duplex and partially half-duplex communication models.Wed, 19 May 2021 06:55:47 +0300https://eccc.weizmann.ac.il/report/2020/116#revision2
Revision 1
| Toward better depth lower bounds: the XOR-KRW conjecture |
Alexander Smal,
Ivan Mihajlin
https://eccc.weizmann.ac.il/report/2020/116#revision1In this paper, we propose a new conjecture, the XOR-KRW conjecture, which is a relaxation of the Karchmer-Raz-Wigderson conjecture [KRW95]. This relaxation is still strong enough to imply $\mathbf{P} \not\subseteq \mathbf{NC}^1$ if proven. We also present a weaker version of this conjecture that might be used for breaking $n^3$ lower bound for De~Morgan formulas. Our study of this conjecture allows us to partially answer an open question stated in [GMWW17] regarding the composition of the universal relation with a function. To be more precise, we prove that there exists a function $g$ such that the composition of the universal relation with $g$ is significantly harder than just a universal relation. The fact that we can only prove the existence of $g$ is an inherent feature of our approach.
The paper's main technical contribution is a method of converting lower bounds for multiplexer-type relations into lower bounds against functions. In order to do this, we develop techniques to lower bound communication complexity using reductions from non-deterministic communication complexity and non-classical models: half-duplex and partially half-duplex communication models.Wed, 25 Nov 2020 12:46:21 +0200https://eccc.weizmann.ac.il/report/2020/116#revision1
Paper TR20-116
| Toward better depth lower bounds: the XOR-KRW conjecture |
Alexander Smal,
Ivan Mihajlin
https://eccc.weizmann.ac.il/report/2020/116In this paper, we propose a new conjecture, the XOR-KRW conjecture, which is a relaxation of the Karchmer-Raz-Wigderson conjecture [KRW95]. This relaxation is still strong enough to imply $\mathbf{P} \not\subseteq \mathbf{NC}^1$ if proven. We also present a weaker version of this conjecture that might be used for breaking $n^3$ lower bound for De~Morgan formulas. Our study of this conjecture allows us to partially answer an open question stated in [GMWW17] regarding the composition of the universal relation with a function. To be more precise, we prove that there exists a function $g$ such that the composition of the universal relation with $g$ is significantly harder than just a universal relation. The fact that we can only prove the existence of $g$ is an inherent feature of our approach.
The paper's main technical contribution is a method of converting lower bounds for multiplexer-type relations into lower bounds against functions. In order to do this, we develop techniques to lower bound communication complexity using reductions from non-deterministic communication complexity and non-classical models: half-duplex and partially half-duplex communication models.Sun, 02 Aug 2020 09:10:06 +0300https://eccc.weizmann.ac.il/report/2020/116