Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RANDOMIZED LOWER BOUND:
Reports tagged with randomized lower bound:
TR26-239 | 6th October 2026
Haoyu Wang, Pei Wu, Guangxu Yang

Exponential Quantum Advantage in Number-on-Forehead Communication

We give the first exponential quantum advantage in the general interactive three-party Number-on-Forehead (NOF) model for a decision problem. Previous separations hold only for restricted protocols like one-way communication for a relation. We construct an explicit partial Boolean function, the Interleaved Unitary Product problem, that requires only $O(\log n)$ quantum ... more >>>




ISSN 1433-8092 | Imprint