A Composition Theorem for Randomized Query Complexity

Abstract

Let the randomized query complexity of a relation for error probability ϵ be denoted by Rϵ(⋅). We prove that for any relation f⊆{0,1}n× and Boolean function g:{0,1}m→{0,1}, R1/3(f∘gn)=Ω(R4/9(f)⋅R1/2−1/n4(g)), where f∘gn is the relation obtained by composing f and g. We also show that R1/3(f∘(g⊕O(logn))n)=Ω(logn⋅R4/9(f)⋅R1/3(g)), where g⊕O(logn) is the function obtained by composing the xor function on O(logn) bits and gt.