文章基本信息

标题：Toward better depth lower bounds: the XOR-KRW conjecture
本地全文：下载
作者：Ivan Mihajlin ; Alexander Smal
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-20
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In 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 P 6⊆ NC1 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 multiplexertype 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.