Exponential Quantum-Classical Gaps in Multiparty Nondeterministic\n Communication Complexity

There are three different types of nondeterminism in quantum communication:\ni) $\\nqp$-communication, ii) $\\qma$-communication, and iii)\n$\\qcma$-communication. In this \\redout{paper} we show that multiparty\n$\\nqp$-communication can be exponentially stronger than $\\qcma$-communication.\nThis also implies an exponential separation with respect to classical\nmultiparty nondeterministic communication complexity. We argue that there\nexists a total function that is hard for $\\qcma$-communication and easy for\n$\\nqp$-communication. The proof of it involves an application of the pattern\ntensor method and a new lower bound for polynomial threshold degree. Another\nimportant consequence of this result is that nondeterministic rank can be\nexponentially lower than the discrepancy bound.\n