Abstract
A natural way to build up functions is to compose them together. For boolean functions f: {0,1}^n -> {0,1} and g: {0,1}^m -> {0,1} we can create a composed function f o g^n : {0,1}^{mn} -> {0,1}, where f o g^n (x_1, ..., x_n) = f(g(x_1), g(x_2), ..., g(x_n)). For most reasonable complexity measures the complexity of f o g^n is at most the complexity of f times the complexity of g. For deterministic query complexity and quantum query complexity this has been shown to be a lower bound as well. For randomized query complexity, however, it is not known if the randomized complexity of f times the randomized complexity of g is a lower bound on the randomized complexity of the composition of f and g. We show an example where f is a relation and g is a partial function where R(f o g^n) <= R(f) * sqrt(R(g)). Thus in this case the perfect composition lower bound cannot hold. For this general setting we show a matching lower bound that R(f o g^n) >= Omega(R(f)*sqrt(R(g))). This generalizes (and slightly improves) the lower bound of Ben-David and Kothari who showed a similar result when f is a partial function and g is total. Our lower bound goes through a new complexity measure we introduce called conflict complexity. This is joint work with Dmitry Gavinsky, Miklos Santha, and Swagato Sanyal.