{
  "annotation_id": "582055cc-c6f8-463a-8366-7d4bfc66222f",
  "date_created": "2026-02-17T05:53:16.066000Z",
  "date_modified": "2026-02-17T05:53:16.066000Z",
  "file_hash": "f2103f85a400e0d650ae819707e4705efd74eca32ccd593590fe58a53a04d1b8",
  "private": false,
  "record": {
    "abstract": "For a (possibly partial) Boolean function $f\\colon\\{0,1\\}^n\\to\\{0,1\\}$ as well as a query complexity measure $M$ which maps Boolean functions to real numbers, define the composition limit of $M$ on $f$ by $M^*(f)=\\lim_{k\\to\\infty} M(f^k)^{1/k}$.\n  We study the composition limits of general measures in query complexity. We show this limit converges under reasonable assumptions about the measure. We then give a surprising result regarding the composition limit of randomized query complexity: we show $R_0^*(f)=\\max\\{R^*(f),C^*(f)\\}$. Among other things, this implies that any bounded-error randomized algorithm for recursive 3-majority can be turned into a zero-error randomized algorithm for the same task. Our result extends also to quantum algorithms: on recursively composed functions, a bounded-error quantum algorithm can be converted into a quantum algorithm that finds a certificate with high probability.\n  Along the way, we prove various combinatorial properties of measures and composition limits.",
    "arxiv_id": "2601.08073",
    "authors": [
      "Bandar Al-Dhalaan",
      "Shalev Ben-David"
    ],
    "categories": [
      "cs.CC",
      "quant-ph"
    ],
    "license": "http://creativecommons.org/licenses/by-sa/4.0/",
    "title": "Monte Carlo to Las Vegas for Recursively Composed Functions",
    "url": "https://arxiv.org/abs/2601.08073",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "95ea95c4-ea85-483d-a504-e6a7669e1c9c",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}