We prove1two results about randomised query complexity $\mathbf{R}(f)$. First, we introduce a linearised complexity measure LR and show that it satisfies an inner-optimal composition theorem: $\mathbf{R}(f^{\circ} g)\geq\Omega(\mathbf{R}(f)\mathbf{L R}(g))$ for all partial f and g, and moreover, LR is the largest possible measure with this property. In particular, LR can be polynomially larger than previous measures that satisfy an inner composition theorem, such as the max-conflict complexity of Gavinsky, Lee, Santha, and Sanyal (ICALP 2019). Our second result addresses a question of Yao (FOCS 1977). He asked if $\epsilon$-error expected query complexity $\overline{\mathbf{R}}_{\epsilon}(f)$ admits a distributional characterisation relative to some hard input distribution. Vereshchagin (TCS 1998) answered this question affirmatively in the bounded-error case. We show that an analogous theorem fails in the small-bias case $\epsilon=1/2-o(1)$.1This is an extended abstract. For the full version of this article, please refer to [BDBGM22].
We prove1two results about randomised query complexity R(f). First, we introduce a linearised complexity measure LR and show that it satisfies an inner-optimal composition theorem: R(f∘g)≥Ω(R(f)LR(g)) for all partial f and g, and moreover, LR is the largest possible measure with this property. In particular, LR can be polynomially larger than previous measures that satisfy an inner composition theorem, such as the max-conflict complexity of Gavinsky, Lee, Santha, and Sanyal (ICALP 2019). Our second result addresses a question of Yao (FOCS 1977). He asked if ϵ-error expected query complexity Rϵ(f) admits a distributional characterisation relative to some hard input distribution. Vereshchagin (TCS 1998) answered this question affirmatively in the bounded-error case. We show that an analogous theorem fails in the small-bias case ϵ=1/2−o(1).1This is an extended abstract. For the full version of this article, please refer to [BDBGM22].
Let Rϵ denote the randomized query complexity for error probability ε, and R:=R1/3 . In this work, we investigate whether a perfect composition theorem R(f∘gn)=Ω(R(f)⋅R(g)) holds for a relation f⊆{0,1}n×S and a total inner function g:{0,1}m→{0,1} . Ben-David and Kothari (ICALP 2016, TOC 2018) showed that R(f∘gn)=Ω(R(f)⋅RS(g)) , where RS is the sabotage complexity, a measure that they defined. Their result holds even when f is any relation and g is any partial function. Ben-David and Kothari asked in their article whether Sabotage complexity RS is asymptotically equivalent to R for total Boolean functions. In this article, we show that RS is asymptotically at least the maximum distributional query complexity for any product distribution (i.e., probability distribution where the individual bits are independently distributed). In light of the minimax theorem, which states that R is the maximum distributional query complexity for any distribution, our result makes progress toward answering the composition question. We prove our result by introducing a novel complexity measure called Rprod , and proving it to be equivalent to RS up to a logarithmic factor. How tight is our bound? We show that our bound is polynomially loose for the complete binary NAND tree function, for which RS is polynomially larger than the distributional query complexity for any product distribution. Our result also confirms that RS and R are asymptotically equivalent for this function. We thus also show a polynomial separation between R and the maximum distributional query complexity for any product distribution which, to our knowledge, was not known prior to our work.
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.
Let R(⋅) stand for the bounded-error randomized query complexity. We show that for any relation f⊆{0,1}n×S and partial Boolean function g⊆{0,1}n×{0,1}, R1/3(f∘gn)=Ω(R4/9(f)⋅R1/3(g)). Independently of us, Gavinsky, Lee and Santha \cite{newcomp} proved this result. By an example demonstrated in their work, this bound is optimal. We prove our result by introducing a novel complexity measure called the \emph{conflict complexity} of a partial Boolean function g, denoted by χ(g), which may be of independent interest. We show that χ(g)=Ω(R(g)) and R(f∘gn)=Ω(R(f)⋅χ(g)).
Let f⊆{0,1}n×Ξ be a relation and g:{0,1}m→{0,1,∗} be a promise function. This work investigates the randomised query complexity of the relation f∘gn⊆{0,1}m⋅n×Ξ, 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∘gn). We show that for every such f and g, R(f∘gn)∈Ω(R(f)⋅R(g)), where R denotes the randomised query complexity. On the other hand, we demonstrate a relation f0 and a promise function g0, such that R(f0)∈Θ(n), R(g0)∈Θ(n) and R(f0∘g0n)∈Θ(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 logn).
Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting Q(f∘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.