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

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 (f g) (f ) (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, (f g) = ( (f ) (g)), where (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 (f g) = (M (f ) (g)) for all f and g, it must hold that (f ) = (M (f )) for all f . We also give a clean characterization of the measure (f ): it satisfies (f ) = ( (f G a p M a j n )/ (G a p M a j n )), where n is the input size of f and G a p M a j n is the n-gap majority function on n bits.