  Let R_eps denote randomized query complexity for error probability eps, and
R:=R_{1/3}. In this work we investigate whether a perfect composition theorem
R(f o g^n)=Omega(R(f).R(g)) holds for a relation f in {0,1}^n * S and a total
inner function g:{0,1}^m \to {0, 1}.
  Let D^(prod) denote the maximum distributional query complexity with respect
to any product (over variables) distribution. In this work we show the
composition theorem R(f o g^n)=Omega(R(f).D^{prod}(g)) up to logarithmic
factors. In light of the minimax theorem which states that R(g) is the maximum
distributional complexity of g over any distribution, our result makes progress
towards answering the composition question. We prove our result by means of a
complexity measure R^(prod)_(eps) that we define for total Boolean functions.
We show it to be equivalent (up to logarithmic factors) to the sabotage
complexity measure RS() defined by Ben-David and Kothari (ICALP 2019): RS(g) =
Theta(R^(prod)_(1/3)(g)) (up to log factors).
  We ask if our bound RS(g) = Omega(D^(prod)(g)) (up to log factors) is tight.
We answer this question in the negative, by showing that for the NAND tree
function, sabotage complexity is polynomially larger than D^(prod). Our proof
yields an alternative and different derivation of the tight lower bound on the
bounded error randomized query complexity of the NAND tree function (originally
proved by Santha in 1985), which may be of independent interest. Our result
gives an explicit polynomial separation between R and D^(prod) which, to our
knowledge, was not known prior to our work.
