Electronic colloquium on computational complexity

The Power of Many Samples in Query Complexity.

Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan

Published Jan 1, 2020• 0 citations

OpenAlex

Abstract

Related papers

The Power of Many Samples in Query Complexity

Andrew Bassilakis, Andrew Drucker, Mika Göös +3 more

Leibniz international proceedings in informaticsJan 1, 20203 citations

Randomized query complexity can beat certificate complexity

Shalev Ben-David, Robin Kothari

A long-standing open question in query complexity asks whether there is a total Boolean function f with R(f) << C(f), where R(f) and C(f) denote its bounded-error randomized query complexity and certificate complexity, respectively. We construct a function with R(f) = O~(sqrt{C(f)}), which is optimal up to log factors. The same function also has $Q(f) = O~(C(f)^{1/4}), where Q(f) is the bounded-error quantum query complexity of f, which is also nearly optimal.

cs.CCCross-listedarXiv:2609.15063Sep 15, 20260 citations

The Power of Many Samples in Query Complexity

Andrew Bassilakis, Andrew Drucker, Mika Göös +3 more

arXiv:2002.10654Feb 25, 20201 citation

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

Shalev Ben-David, Eric Blais

Annual Symposium on Foundations of Computer ScienceNov 1, 20209 citations

Distributional Quantum Query Complexity

Shalev Ben-David, M. H. Ebtehaj

quant-pharXiv:2610.06835Oct 6, 20260 citations

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

Shalev Ben-David, Eric Blais

arXiv:2002.10809Feb 25, 20206 citations

Electronic colloquium on computational complexity

The Power of Many Samples in Query Complexity.

Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan

Published Jan 1, 2020• 0 citations

OpenAlex

Abstract

Related papers

The Power of Many Samples in Query Complexity

Andrew Bassilakis, Andrew Drucker, Mika Göös +3 more

The randomized query complexity 𝖱(f) of a boolean function f: {0,1}ⁿ → {0,1} is famously characterized (via Yao’s minimax) by the least number of queries needed to distinguish a distribution 𝒟₀ over 0-inputs from a distribution 𝒟₁ over 1-inputs, maximized over all pairs (𝒟₀,𝒟₁). We ask: Does this task become easier if we allow query access to infinitely many samples from either 𝒟₀ or 𝒟₁? We show the answer is no: There exists a hard pair (𝒟₀,𝒟₁) such that distinguishing 𝒟₀^∞ from 𝒟₁^∞ requires Θ(𝖱(f)) many queries. As an application, we show that for any composed function f∘g we have 𝖱(f∘g) ≥ Ω(fbs(f)𝖱(g)) where fbs denotes fractional block sensitivity.The randomized query complexity 𝖱(f) of a boolean function f: {0,1}ⁿ → {0,1} is famously characterized (via Yao’s minimax) by the least number of queries needed to distinguish a distribution 𝒟₀ over 0-inputs from a distribution 𝒟₁ over 1-inputs, maximized over all pairs (𝒟₀,𝒟₁). We ask: Does this task become easier if we allow query access to infinitely many samples from either 𝒟₀ or 𝒟₁? We show the answer is no: There exists a hard pair (𝒟₀,𝒟₁) such that distinguishing 𝒟₀^∞ from 𝒟₁^∞ requires Θ(𝖱(f)) many queries. As an application, we show that for any composed function f∘g we have 𝖱(f∘g) ≥ Ω(fbs(f)𝖱(g)) where fbs denotes fractional block sensitivity.

Leibniz international proceedings in informaticsJan 1, 20203 citations

Randomized query complexity can beat certificate complexity

Shalev Ben-David, Robin Kothari

cs.CCCross-listedarXiv:2609.15063Sep 15, 20260 citations

The Power of Many Samples in Query Complexity

Andrew Bassilakis, Andrew Drucker, Mika Göös +3 more

The randomized query complexity $R(f)$ of a boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is famously characterized (via Yao's minimax) by the least number of queries needed to distinguish a distribution $D_0$ over $0$ -inputs from a distribution $D_1$ over $1$ -inputs, maximized over all pairs $(D_0,D_1)$ . We ask: Does this task become easier if we allow query access to infinitely many samples from either $D_0$ or $D_1$ ? We show the answer is no: There exists a hard pair $(D_0,D_1)$ such that distinguishing $D_0^\infty$ from $D_1^\infty$ requires $Θ(R(f))$ many queries. As an application, we show that for any composed function $f\circ g$ we have $R(f\circ g) \geq Ω(\mathrm{fbs}(f)R(g))$ where $\mathrm{fbs}$ denotes fractional block sensitivity.The randomized query complexity $R(f)$ of a boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is famously characterized (via Yao's minimax) by the least number of queries needed to distinguish a distribution $D_0$ over $0$-inputs from a distribution $D_1$ over $1$-inputs, maximized over all pairs $(D_0,D_1)$. We ask: Does this task become easier if we allow query access to infinitely many samples from either $D_0$ or $D_1$? We show the answer is no: There exists a hard pair $(D_0,D_1)$ such that distinguishing $D_0^\infty$ from $D_1^\infty$ requires $Θ(R(f))$ many queries. As an application, we show that for any composed function $f\circ g$ we have $R(f\circ g) \geq Ω(\mathrm{fbs}(f)R(g))$ where $\mathrm{fbs}$ denotes fractional block sensitivity.

arXiv:2002.10654Feb 25, 20201 citation

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

Distributional Quantum Query Complexity

Shalev Ben-David, M. H. Ebtehaj

Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting $Q(f\circ g)=Θ(Q(f)Q(g))$ for all Boolean functions $f$ and $g$ ; a direct sum theorem asserting that computing $k$ copies of a function (or search problem) costs $Ω(k)$ times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires $Ω(k)$ times the cost of computing one copy to bounded error. However, all of these results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution $μ$ over inputs, the direct sum theorem says nothing about the quantum query complexity of computing $k$ copies of $f$ when the input comes from the product distribution $μ^k$ instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions. In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new ``multiplicative'' variant of the $γ_2$ norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new ``Shaltiel-free'' measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting $Q(f\circ g)=Θ(Q(f)Q(g))$ for all Boolean functions $f$ and $g$; a direct sum theorem asserting that computing $k$ copies of a function (or search problem) costs $Ω(k)$ times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires $Ω(k)$ times the cost of computing one copy to bounded error. However, all of these results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution $μ$ over inputs, the direct sum theorem says nothing about the quantum query complexity of computing $k$ copies of $f$ when the input comes from the product distribution $μ^k$ instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions. In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new ``multiplicative'' variant of the $γ_2$ norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new ``Shaltiel-free'' measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.

quant-pharXiv:2610.06835Oct 6, 20260 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

The randomized query complexity

R(f)

of a boolean function

f\colon\{0,1\}^n\to\{0,1\}

is famously characterized (via Yao's minimax) by the least number of queries needed to distinguish a distribution

D_0

over

0

-inputs from a distribution

D_1

over

1

-inputs, maximized over all pairs

(D_0,D_1)

. We ask: Does this task become easier if we allow query access to infinitely many samples from either

D_0

D_1

? We show the answer is no: There exists a hard pair

(D_0,D_1)

such that distinguishing

D_0^\infty

from

D_1^\infty

requires

Θ(R(f))

many queries. As an application, we show that for any composed function

f\circ g

we have

R(f\circ g) \geq Ω(\mathrm{fbs}(f)R(g))

where

\mathrm{fbs}

denotes fractional block sensitivity.

Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting

Q(f\circ g)=Θ(Q(f)Q(g))

for all Boolean functions

f

and

g

; a direct sum theorem asserting that computing

k

copies of a function (or search problem) costs

Ω(k)

times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires

Ω(k)

times the cost of computing one copy to bounded error. However, all of these results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution

μ

over inputs, the direct sum theorem says nothing about the quantum query complexity of computing

k

copies of

f

when the input comes from the product distribution

μ^k

instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions. In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new ``multiplicative'' variant of the

γ_2

norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new ``Shaltiel-free'' measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.

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.