ACM Symposium on Theory of Computing (STOC)

Monte Carlo to Las Vegas for Recursively Composed Functions

Bandar Al-Dhalaan, Shalev Ben-David

Published Jun 9, 2026• 0 citations

Abstract

For a (possibly partial) Boolean function f:{0,1}n→{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)=limk→∞ M(fk)1/k.

DOI: 10.1145/3798129.3800897

Related papers

Monte Carlo to Las Vegas for Recursively Composed Functions

Bandar Al-Dhalaan, Shalev Ben-David

cs.CCCross-listedarXiv:2601.08073Jan 14, 20260 citations

Average-case query complexity of fixed-weight boolean functions and k-CNFs

Yuan Li, Mingjun Liu, Haowei Wu +1 more

Theoretical Computer ScienceAug 8, 20260 citations

Query Complexity of Boolean Functions on the Middle Slice of the Cube

Dániel Gerbner, Balázs Keszegh, Dániel T. Nagy +4 more

Jan 1, 20230 citations

A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions

Shalev Ben-David, Eric Blais

arXiv:2002.10809Feb 25, 20206 citations

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity

Miklós Sántha, Dmitry Gavinsky, Troy Lee +1 more

Jan 1, 20190 citations

Lower Bounds for the Number of Random Bits in Monte Carlo Algorithms

Stefan Heinrich

arXiv:2012.12774Springer proceedings in mathematics & statisticsJan 1, 20222 citations

ACM Symposium on Theory of Computing (STOC)

Monte Carlo to Las Vegas for Recursively Composed Functions

Bandar Al-Dhalaan, Shalev Ben-David

Published Jun 9, 2026• 0 citations

Publisher

Abstract

DOI: 10.1145/3798129.3800897

Related papers

Monte Carlo to Las Vegas for Recursively Composed Functions

Bandar Al-Dhalaan, Shalev Ben-David

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 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. Along the way, we prove various combinatorial properties of measures and composition limits.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 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. Along the way, we prove various combinatorial properties of measures and composition limits.

cs.CCCross-listedarXiv:2601.08073Jan 14, 20260 citations

Average-case query complexity of fixed-weight boolean functions and k-CNFs

Yuan Li, Mingjun Liu, Haowei Wu +1 more

Theoretical Computer ScienceAug 8, 20260 citations

Query Complexity of Boolean Functions on the Middle Slice of the Cube

Dániel Gerbner, Balázs Keszegh, Dániel T. Nagy +4 more

Jan 1, 20230 citations

A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions

Shalev Ben-David, Eric Blais

We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions $f$ and $g$ such that $R(f\circ g)\ll R(f) R(g)$ . In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of $f$ ). Second, we show that for all $f$ and $g$ , $R(f\circ g)=Ω(\mathop{noisyR}(f)\cdot R(g))$ , where $\mathop{noisyR}(f)$ is a measure describing the cost of computing $f$ on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure $M(\cdot)$ satisfying $R(f\circ g)=Ω(M(f)R(g))$ for all $f$ and $g$ , it must hold that $\mathop{noisyR}(f)=Ω(M(f))$ for all $f$ . We also give a clean characterization of the measure $\mathop{noisyR}(f)$ : it satisfies $\mathop{noisyR}(f)=Θ(R(f\circ gapmaj_n)/R(gapmaj_n))$ , where $n$ is the input size of $f$ and $gapmaj_n$ is the $\sqrt{n}$ -gap majority function on $n$ bits.We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions $f$ and $g$ such that $R(f\circ g)\ll R(f) R(g)$. In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of $f$). Second, we show that for all $f$ and $g$, $R(f\circ g)=Ω(\mathop{noisyR}(f)\cdot R(g))$, where $\mathop{noisyR}(f)$ is a measure describing the cost of computing $f$ on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure $M(\cdot)$ satisfying $R(f\circ g)=Ω(M(f)R(g))$ for all $f$ and $g$, it must hold that $\mathop{noisyR}(f)=Ω(M(f))$ for all $f$. We also give a clean characterization of the measure $\mathop{noisyR}(f)$: it satisfies $\mathop{noisyR}(f)=Θ(R(f\circ gapmaj_n)/R(gapmaj_n))$, where $n$ is the input size of $f$ and $gapmaj_n$ is the $\sqrt{n}$-gap majority function on $n$ bits.

arXiv:2002.10809Feb 25, 20206 citations

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity

Miklós Sántha, Dmitry Gavinsky, Troy Lee +1 more

Let $R_\epsilon(\cdot)$ stand for the bounded-error randomized query complexity with error $\epsilon > 0$ . For any relation $f \subseteq \{0,1\}^n \times S$ and partial Boolean function $g \subseteq \{0,1\}^m \times \{0,1\}$ , we show that $R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \sqrt{R_{1/3}(g)})$ , where $f \circ g^n \subseteq (\{0,1\}^m)^n \times S$ is the composition of $f$ and $g$ . We give an example of a relation $f$ and partial Boolean function $g$ for which this lower bound is tight. We prove our composition theorem by introducing a new complexity measure, the max conflict complexity $\bar \chi(g)$ of a partial Boolean function $g$ . We show $\bar \chi(g) \in \Omega(\sqrt{R_{1/3}(g)})$ for any (partial) function $g$ and $R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \bar \chi(g))$ ; these two bounds imply our composition result. We further show that $\bar \chi(g)$ is always at least as large as the sabotage complexity of $g$ , introduced by Ben-David and Kothari.Let $R_\epsilon(\cdot)$ stand for the bounded-error randomized query complexity with error $\epsilon > 0$. For any relation $f \subseteq \{0,1\}^n \times S$ and partial Boolean function $g \subseteq \{0,1\}^m \times \{0,1\}$, we show that $R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \sqrt{R_{1/3}(g)})$, where $f \circ g^n \subseteq (\{0,1\}^m)^n \times S$ is the composition of $f$ and $g$. We give an example of a relation $f$ and partial Boolean function $g$ for which this lower bound is tight. We prove our composition theorem by introducing a new complexity measure, the max conflict complexity $\bar \chi(g)$ of a partial Boolean function $g$. We show $\bar \chi(g) \in \Omega(\sqrt{R_{1/3}(g)})$ for any (partial) function $g$ and $R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \bar \chi(g))$; these two bounds imply our composition result. We further show that $\bar \chi(g)$ is always at least as large as the sabotage complexity of $g$, introduced by Ben-David and Kothari.

Jan 1, 20190 citations

Lower Bounds for the Number of Random Bits in Monte Carlo Algorithms

Stefan Heinrich

arXiv:2012.12774Springer proceedings in mathematics & statisticsJan 1, 20222 citations

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

f

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 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. Along the way, we prove various combinatorial properties of measures and composition limits.

f

and

g

such that

R(f\circ g)\ll R(f) R(g)

. In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of

f

). Second, we show that for all

f

and

g

R(f\circ g)=Ω(\mathop{noisyR}(f)\cdot R(g))

, where

\mathop{noisyR}(f)

is a measure describing the cost of computing

f

on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure

M(\cdot)

satisfying

R(f\circ g)=Ω(M(f)R(g))

for all

f

and

g

, it must hold that

\mathop{noisyR}(f)=Ω(M(f))

for all

f

. We also give a clean characterization of the measure

\mathop{noisyR}(f)

: it satisfies

\mathop{noisyR}(f)=Θ(R(f\circ gapmaj_n)/R(gapmaj_n))

, where

n

is the input size of

f

and

gapmaj_n

is the

\sqrt{n}

-gap majority function on

n

bits.

Let

R_\epsilon(\cdot)

stand for the bounded-error randomized query complexity with error

\epsilon > 0

. For any relation

f \subseteq \{0,1\}^n \times S

and partial Boolean function

g \subseteq \{0,1\}^m \times \{0,1\}

, we show that

R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \sqrt{R_{1/3}(g)})

, where

f \circ g^n \subseteq (\{0,1\}^m)^n \times S

is the composition of

f

and

g

. We give an example of a relation

f

and partial Boolean function

g

for which this lower bound is tight. We prove our composition theorem by introducing a new complexity measure, the max conflict complexity

\bar \chi(g)

of a partial Boolean function

g

. We show

\bar \chi(g) \in \Omega(\sqrt{R_{1/3}(g)})

for any (partial) function

g

and

R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \bar \chi(g))

; these two bounds imply our composition result. We further show that

\bar \chi(g)

is always at least as large as the sabotage complexity of

g

, introduced by Ben-David and Kothari.