{
  "annotation_id": "fa4c159d-f292-43c7-9bbd-9a610b877ad2",
  "date_created": "2026-03-02T18:01:48.535000Z",
  "date_modified": "2026-03-02T18:01:48.535000Z",
  "file_hash": "0b4667104d607ca0b7379c60717f6e5bebd63c59a513d61b5dc409acc1b98469",
  "private": false,
  "record": {
    "abstract": "We completely (that is, up to a logarithmic factor) characterize the\nbounded-error quantum communication complexity of every predicate $f(x,y)$\ndepending only on $|x\\cap y|$ ($x,y\\subseteq [n]$). Namely, for a predicate $D$\non $\\{0,1,...,n\\}$ let $\\ell_0(D)\\df \\max\\{\\ell : 1\\leq\\ell\\leq n/2\\land\nD(\\ell)\\not\\equiv D(\\ell-1)\\}$ and $\\ell_1(D)\\df \\max\\{n-\\ell : n/2\\leq\\ell \u003c\nn\\land D(\\ell)\\not\\equiv D(\\ell+1)\\}$. Then the bounded-error quantum\ncommunication complexity of $f_D(x,y) = D(|x\\cap y|)$ is equal (again, up to a\nlogarithmic factor) to $\\sqrt{n\\ell_0(D)}+\\ell_1(D)$. In particular, the\ncomplexity of the set disjointness predicate is $\\Omega(\\sqrt n)$. This result\nholds both in the model with prior entanglement and without it.",
    "arxiv_id": "quant-ph/0204025",
    "authors": [
      "Alexander Razborov"
    ],
    "categories": [
      "quant-ph"
    ],
    "doi": "10.1070/IM2003v067n01ABEH000422",
    "journal_ref": "Izvestiya of the Russian Academy of Science, mathematics, Vol. 67,\n  No 1, 2003, pp. 159-176 (145-159 in Engl. transl.)",
    "title": "Quantum communication complexity of symmetric predicates",
    "url": "https://arxiv.org/abs/quant-ph/0204025"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "878b923a-d2dd-4322-9556-d95ff71f0c24",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}