Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with nondeterministic communication complexity:
TR13-110 | 12th August 2013
Xiaoming Sun, Marcos Villagra

Exponential Quantum-Classical Gaps in Multiparty Nondeterministic Communication Complexity

There are three different types of nondeterminism in quantum communication: i) $\nqp$-communication, ii) $\qma$-communication, and iii) $\qcma$-communication. In this \redout{paper} we show that multiparty $\nqp$-communication can be exponentially stronger than $\qcma$-communication. This also implies an exponential separation with respect to classical multiparty nondeterministic communication complexity. We argue that there exists ... more >>>

TR16-054 | 11th April 2016
Omri Weinstein, Huacheng Yu

Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication

This paper develops a new technique for proving amortized, randomized cell-probe lower bounds on dynamic
data structure problems. We introduce a new randomized nondeterministic four-party communication model
that enables "accelerated", error-preserving simulations of dynamic data structures.

We use this technique to prove an $\Omega(n\left(\log n/\log\log n\right)^2)$ cell-probe ... more >>>

ISSN 1433-8092 | Imprint