Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > PARTIALLY HALF-DUPLEX COMMUNICATION COMPLEXITY:
Reports tagged with partially half-duplex communication complexity:
TR23-151 | 11th October 2023
Hao Wu

An Improved Composition Theorem of a Universal Relation and Most Functions via Effective Restriction

Revisions: 1

One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, to tackle this problem Karchmer, Raz and Wigderson proposed the KRW conjecture about composition of two functions. While this conjecture seems out of our current reach, some relaxed conjectures are ... more >>>




ISSN 1433-8092 | Imprint