Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: A Note on Shared Randomness and Shared Entanglement in Communication   We consider several models of 1-round classical and quantum communication,
some of these models have not been defined before. We "almost separate" the
models of simultaneous quantum message passing with shared entanglement and the
model of simultaneous quantum message passing with shared randomness. We define
a relation which can be efficiently exactly solved in the first model but
cannot be solved efficiently, either exactly or in 0-error setup in the second
model. In fact, our relation is exactly solvable even in a more restricted
model of simultaneous classical message passing with shared entanglement.
  As our second contribution we strengthen a result by Yao that a "very short"
protocol from the model of simultaneous classical message passing with shared
randomness can be simulated in the model of simultaneous quantum message
passing: for a boolean function f, QII(f) \in exp(O(RIIp(f))) log n.
  We show a similar result for protocols from a (stronger) model of 1-way
classical message passing with shared randomness: QII(f) \in exp(O(RIp(f))) log
n.
  We demonstrate a problem whose efficient solution in the model of
simultaneous quantum message passing follows from our result but not from
Yao's.

26
The categories of this paper are: bayes-an
6
The categories of this paper are: astro-ph
36
The categories of this paper are: cmp-lg
27
The categories of this paper are: comp-gas
9
The categories of this paper are: nlin
12
The categories of this paper are: nucl-th
8
The categories of this paper are: hep-ex
2
The categories of this paper are: math
30
The categories of this paper are: q-alg
3
The categories of this paper are: physics
32
The categories of this paper are: atom-ph
25
The categories of this paper are: patt-sol
23
The categories of this paper are: solv-int
34
The categories of this paper are: chem-ph
7
The categories of this paper are: hep-th
14
The categories of this paper are: math-ph