Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with universal relation:
TR17-128 | 15th August 2017
Or Meir

The Direct Sum of Universal Relations

Revisions: 3 , Comments: 1

The universal relation is the communication problem in which Alice and Bob get as inputs two distinct strings, and they are required to find a coordinate on which the strings differ. The study of this problem is motivated by its connection to Karchmer-Wigderson relations, which are communication problems that are ... more >>>

TR20-116 | 1st August 2020
Ivan Mihajlin, Alexander Smal

Toward better depth lower bounds: the XOR-KRW conjecture

Revisions: 2

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 ... more >>>

ISSN 1433-8092 | Imprint