. 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.

DOI: 10.48550/arxiv.2002.10809

Related papers

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

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°g) ≪ 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°g) = Ω(noisyR(f) R(g)), where 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(·) satisfying R(f°g)=Ω(M(f)R(g)) for all f and g, it must hold that noisyR(f)=Ω(M(f)) for all f. We also give a clean characterization of the measure noisyR(f): it satisfies noisyR(f)=Θ(R(f°GapMajn)/R(GapMajn)), where n is the input size of f and GapMajn is the √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°g) ≪ 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°g) = Ω(noisyR(f) R(g)), where 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(·) satisfying R(f°g)=Ω(M(f)R(g)) for all f and g, it must hold that noisyR(f)=Ω(M(f)) for all f. We also give a clean characterization of the measure noisyR(f): it satisfies noisyR(f)=Θ(R(f°GapMajn)/R(GapMajn)), where n is the input size of f and GapMajn is the √n-gap majority function on n bits.

Annual Symposium on Foundations of Computer ScienceNov 1, 20209 citations

No Perfect Randomized Composition

Alex Meiburg

Does computing a composition of total Boolean functions require the product of the randomized query complexities of its factors? We give a negative answer. There are families of total functions $f,g$ such that $R(f\circ g) =Θ\!\left(\frac1{\log R(g)}\right)R(f)R(g)$ This result requires first separating linearized query complexity $\LR$, as well as noisy randomized query complexity $noisyR$ , from standard randomized query complexity $R$ . Both constructions essentially come from totalizing existing partial function separations, albeit via different techniques. By adapting these techniques, we also construct total functions separating every adjacent pair in the chain from sabotage $RS$ , max-conflict $\barχ$ , and linearised query complexity $LR$ . We show that AND-of-ORs separates conflict $χ$ from max-conflict $\barχ$ complexity and makes conflict and sabotage incomparable. Finally, randomized complexity can be smaller than its composition limit $R^*$ by the maximal factor $Θ(\log R)$ . The total--total composition separation is also formalized in Lean.Does computing a composition of total Boolean functions require the product of the randomized query complexities of its factors? We give a negative answer. There are families of total functions $f,g$ such that $R(f\circ g) =Θ\!\left(\frac1{\log R(g)}\right)R(f)R(g)$ This result requires first separating linearized query complexity $\LR$, as well as noisy randomized query complexity $noisyR$, from standard randomized query complexity $R$. Both constructions essentially come from totalizing existing partial function separations, albeit via different techniques. By adapting these techniques, we also construct total functions separating every adjacent pair in the chain from sabotage $RS$, max-conflict $\barχ$, and linearised query complexity $LR$. We show that AND-of-ORs separates conflict $χ$ from max-conflict $\barχ$ complexity and makes conflict and sabotage incomparable. Finally, randomized complexity can be smaller than its composition limit $R^*$ by the maximal factor $Θ(\log R)$. The total--total composition separation is also formalized in Lean.

arXiv:2610.31638Oct 22, 20260 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

On the randomised query complexity of composition

Gavinsky, Dmytro, Troy Lee, Miklós Sántha

Let $f\subseteq\{0,1\}^n\timesΞ$ be a relation and $g:\{0,1\}^m\to\{0,1,*\}$ be a promise function. This work investigates the randomised query complexity of the relation $f\circ g^n\subseteq\{0,1\}^{m\cdot n}\timesΞ$ , which can be viewed as one of the most general cases of composition in the query model (letting $g$ be a relation seems to result in a rather unnatural definition of $f\circ g^n$ ). We show that for every such $f$ and $g$ , $\mathcal R(f\circ g^n) \in Ω(\mathcal R(f)\cdot\sqrt{\mathcal R(g)}),$ where $\mathcal R$ denotes the randomised query complexity. On the other hand, we demonstrate a relation $f_0$ and a promise function $g_0$ , such that $\mathcal R(f_0)\inΘ(\sqrt n)$ , $\mathcal R(g_0)\inΘ(n)$ and $\mathcal R(f_0\circ g_0^n)\inΘ(n)$ $-$ that is, our composition statement is tight. To the best of our knowledge, there was no known composition theorem for the randomised query complexity of relations or promise functions (and for the special case of total functions our lower bound gives multiplicative improvement of $\sqrt{\log n}$ ).Let $f\subseteq\{0,1\}^n\timesΞ$ be a relation and $g:\{0,1\}^m\to\{0,1,*\}$ be a promise function. This work investigates the randomised query complexity of the relation $f\circ g^n\subseteq\{0,1\}^{m\cdot n}\timesΞ$, which can be viewed as one of the most general cases of composition in the query model (letting $g$ be a relation seems to result in a rather unnatural definition of $f\circ g^n$). We show that for every such $f$ and $g$, $$\mathcal R(f\circ g^n) \in Ω(\mathcal R(f)\cdot\sqrt{\mathcal R(g)}),$$ where $\mathcal R$ denotes the randomised query complexity. On the other hand, we demonstrate a relation $f_0$ and a promise function $g_0$, such that $\mathcal R(f_0)\inΘ(\sqrt n)$, $\mathcal R(g_0)\inΘ(n)$ and $\mathcal R(f_0\circ g_0^n)\inΘ(n)$ $-$ that is, our composition statement is tight. To the best of our knowledge, there was no known composition theorem for the randomised query complexity of relations or promise functions (and for the special case of total functions our lower bound gives multiplicative improvement of $\sqrt{\log n}$).

arXiv:1801.02226Jan 7, 20185 citations

Randomized query complexity of sabotaged and composed functions

Shalev Ben-David, Robin Kothari

We study the composition question for bounded-error randomized query complexity: Is R(f o g) = Omega(R(f) R(g)) for all Boolean functions f and g? We show that inserting a simple Boolean function h, whose query complexity is only Theta(log R(g)), in between f and g allows us to prove R(f o h o g) = Omega(R(f) R(h) R(g)). We prove this using a new lower bound measure for randomized query complexity we call randomized sabotage complexity, RS(f). Randomized sabotage complexity has several desirable properties, such as a perfect composition theorem, RS(f o g) >= RS(f) RS(g), and a composition theorem with randomized query complexity, R(f o g) = Omega(R(f) RS(g)). It is also a quadratically tight lower bound for total functions and can be quadratically superior to the partition bound, the best known general lower bound for randomized query complexity. Using this technique we also show implications for lifting theorems in communication complexity. We show that a general lifting theorem for zero-error randomized protocols implies a general lifting theorem for bounded-error protocols.We study the composition question for bounded-error randomized query complexity: Is R(f o g) = Omega(R(f) R(g)) for all Boolean functions f and g? We show that inserting a simple Boolean function h, whose query complexity is only Theta(log R(g)), in between f and g allows us to prove R(f o h o g) = Omega(R(f) R(h) R(g)). We prove this using a new lower bound measure for randomized query complexity we call randomized sabotage complexity, RS(f). Randomized sabotage complexity has several desirable properties, such as a perfect composition theorem, RS(f o g) >= RS(f) RS(g), and a composition theorem with randomized query complexity, R(f o g) = Omega(R(f) RS(g)). It is also a quadratically tight lower bound for total functions and can be quadratically superior to the partition bound, the best known general lower bound for randomized query complexity. Using this technique we also show implications for lifting theorems in communication complexity. We show that a general lifting theorem for zero-error randomized protocols implies a general lifting theorem for bounded-error protocols.

arXiv:1605.09071Electronic colloquium on computational complexityMay 29, 201611 citations

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

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.

Does computing a composition of total Boolean functions require the product of the randomized query complexities of its factors? We give a negative answer. There are families of total functions

f,g

such that

R(f\circ g) =Θ\!\left(\frac1{\log R(g)}\right)R(f)R(g)

This result requires first separating linearized query complexity $\LR$, as well as noisy randomized query complexity

noisyR

, from standard randomized query complexity

R

. Both constructions essentially come from totalizing existing partial function separations, albeit via different techniques. By adapting these techniques, we also construct total functions separating every adjacent pair in the chain from sabotage

RS

, max-conflict

\barχ

, and linearised query complexity

LR

. We show that AND-of-ORs separates conflict

χ

from max-conflict

\barχ

complexity and makes conflict and sabotage incomparable. Finally, randomized complexity can be smaller than its composition limit

R^*

by the maximal factor

Θ(\log R)

. The total--total composition separation is also formalized in Lean.

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

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

be a relation and

g:\{0,1\}^m\to\{0,1,*\}

be a promise function. This work investigates the randomised query complexity of the relation

f\circ g^n\subseteq\{0,1\}^{m\cdot n}\timesΞ

, which can be viewed as one of the most general cases of composition in the query model (letting

g

be a relation seems to result in a rather unnatural definition of

f\circ g^n

). We show that for every such

f

and

g

\mathcal R(f\circ g^n) \in Ω(\mathcal R(f)\cdot\sqrt{\mathcal R(g)}),

where

\mathcal R

denotes the randomised query complexity. On the other hand, we demonstrate a relation

f_0

and a promise function

g_0

, such that

\mathcal R(f_0)\inΘ(\sqrt n)

\mathcal R(g_0)\inΘ(n)

and

\mathcal R(f_0\circ g_0^n)\inΘ(n)

-

that is, our composition statement is tight. To the best of our knowledge, there was no known composition theorem for the randomised query complexity of relations or promise functions (and for the special case of total functions our lower bound gives multiplicative improvement of

\sqrt{\log n}

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.