{
  "annotation_id": "73c137c9-dd2a-4d4b-9a21-19237b53002d",
  "date_created": "2026-03-02T18:01:56.614000Z",
  "date_modified": "2026-03-02T18:01:56.614000Z",
  "file_hash": "676ea0c4817952ccf1ef37b4b513bfa68a618e4ab5ba641e21eb4576ad6afe0d",
  "private": false,
  "record": {
    "abstract": "We consider the class of functions whose value depends only on the\nintersection of the input X_1,X_2, ..., X_t; that is, for each F in this class\nthere is an f_F: 2^{[n]} \\to {0,1}, such that F(X_1,X_2, ..., X_t) = f_F(X_1\n\\cap X_2 \\cap ... \\cap X_t). We show that the t-party k-round communication\ncomplexity of F is Omega(s_m(f_F)/(k^2)), where s_m(f_F) stands for the\n`monotone sensitivity of f_F\u0027 and is defined by s_m(f_F) \\defeq max_{S\\subseteq\n[n]} |{i: f_F(S \\cup {i}) \\neq f_F(S)|. For two-party quantum communication\nprotocols for the set disjointness problem, this implies that the two parties\nmust exchange Omega(n/k^2) qubits. For k=1, our lower bound matches the\nOmega(n) lower bound observed by Buhrman and de Wolf (based on a result of\nNayak, and for 2 \u003c= k \u003c= n^{1/4}, improves the lower bound of Omega(sqrt{n})\nshown by Razborov. (For protocols with no restrictions on the number of rounds,\nwe can conclude that the two parties must exchange Omega(n^{1/3}) qubits. This,\nhowever, falls short of the optimal Omega(sqrt{n}) lower bound shown by\nRazborov.)",
    "arxiv_id": "quant-ph/0303138",
    "authors": [
      "Rahul Jain",
      "Jaikumar Radhakrishnan",
      "Pranab Sen"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "A lower bound for bounded round quantum communication complexity of set   disjointness",
    "url": "https://arxiv.org/abs/quant-ph/0303138"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "211777d0-1a60-4c17-ad36-b1742d413ce2",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}