Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Xiang Meng:

TR22-130 | 15th September 2022
Hamed Hatami, Kaave Hosseini, Xiang Meng

A Borsuk-Ulam lower bound for sign-rank and its application

We introduce a new topological argument based on the Borsuk-Ulam theorem to prove a lower bound on sign-rank.

This result implies the strongest possible separation between randomized and unbounded-error communication complexity. More precisely, we show that for a particular range of parameters, the randomized communication complexity of ... more >>>

ISSN 1433-8092 | Imprint