Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR20-116 | 1st August 2020 01:05

#### Toward better depth lower bounds: the XOR-KRW conjecture

TR20-116
Authors: Ivan Mihajlin, Alexander Smal
Publication: 2nd August 2020 09:10
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 $\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.