{"id":"arxiv/2601.08073","url":"https://arxiv.org/abs/2601.08073","tags":["cs.CC","quant-ph"],"score":0,"title":"Monte Carlo to Las Vegas for Recursively Composed Functions","domain":"cs.CC","source":"arxiv","authors":["Bandar Al-Dhalaan","Shalev Ben-David"],"reviews":0,"subject":"cs.CC","summary":"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}$. 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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-12","reactions":{}}