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⊆{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).
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.
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.
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ϵ 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 study the composition question for bounded-error randomized query complexity: Is R(f circ g) = Omega(R(f)R(g))? We show that inserting a simple function h, whose query complexity is onlyTheta(log R(g)), in between f and g allows us to prove R(f circ h circ 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 circ g) >= RS(f) RS(g), and a composition theorem with randomized query complexity, R(f circ 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 from zero-error randomized query to communication complexity implies a similar result for bounded-error algorithms for all total functions.