For any relation f subseteq {0,1}^n x S and any partial Boolean function g:{0,1}^m -> {0,1,*}, we show that R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * sqrt{R_{1/3}(g)}) , where R_epsilon(*) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g^n subseteq ({0,1}^m)^n x S denotes the composition of f with n instances of g. The new composition theorem is optimal, at least, for the general case of relational problems: A relation f_0 and a partial Boolean function g_0 are constructed, such that R_{4/9}(f_0) in Theta(sqrt n), R_{1/3}(g_0)in Theta(n) and R_{1/3}(f_0 o g_0^n) in Theta(n). The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by bar{chi}(*). Its investigation shows that bar{chi}(g) in Omega(sqrt{R_{1/3}(g)}) for any partial Boolean function g and R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * bar{chi}(g)) for any relation f, which readily implies the composition statement. It is further shown that bar{chi}(g) is always at least as large as the sabotage complexity of g.
For any relation f subseteq {0,1}^n x S and any partial Boolean function g:{0,1}^m -> {0,1,}, we show that R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * sqrt{R_{1/3}(g)}) , where R_epsilon() stands for the bounded-error randomized query complexity with error at most epsilon, and f o g^n subseteq ({0,1}^m)^n x S denotes the composition of f with n instances of g. The new composition theorem is optimal, at least, for the general case of relational problems: A relation f_0 and a partial Boolean function g_0 are constructed, such that R_{4/9}(f_0) in Theta(sqrt n), R_{1/3}(g_0)in Theta(n) and R_{1/3}(f_0 o g_0^n) in Theta(n). The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by bar{chi}(*). Its investigation shows that bar{chi}(g) in Omega(sqrt{R_{1/3}(g)}) for any partial Boolean function g and R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * bar{chi}(g)) for any relation f, which readily implies the composition statement. It is further shown that bar{chi}(g) is always at least as large as the sabotage complexity of g.
Let Rϵ(⋅) stand for the bounded-error randomized query complexity with error ϵ>0. For any relation f⊆{0,1}n×S and partial Boolean function g⊆{0,1}m×{0,1}, we show that R1/3(f∘gn)∈Ω(R4/9(f)⋅R1/3(g)), where f∘gn⊆({0,1}m)n×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 χˉ(g) of a partial Boolean function g. We show χˉ(g)∈Ω(R1/3(g)) for any (partial) function g and R1/3(f∘gn)∈Ω(R4/9(f)⋅χˉ(g)); these two bounds imply our composition result. We further show that χˉ(g) is always at least as large as the sabotage complexity of g, introduced by Ben-David and Kothari.
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 the randomized query complexity of a relation for error probability epsilon be denoted by R_epsilon(). We prove that for any relation f contained in {0,1}^n times R and Boolean function g:{0,1}^m -> {0,1}, R_{1/3}(f o g^n) = Omega(R_{4/9}(f).R_{1/2-1/n^4}(g)), where f o g^n is the relation obtained by composing f and g. We also show using an XOR lemma that R_{1/3}(f o (g^{xor}_{O(log n)})^n) = Omega(log n . R_{4/9}(f) . R_{1/3}(g))$, where g^{xor}_{O(log n)} is the function obtained by composing the XOR function on O(log n) bits and g.
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.
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.
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 R0∗(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.
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.