On a Composition Theorem for Randomized Query Complexity
summary
Proves a composition lower bound showing randomized query complexity can drop to R(F)·√R(G) and gives a matching example: an outer relation with R(F)=Θ(√n) and an inner partial function G (a gap-Hamming gadget) with R(G)=Θ(n) yet R(F◦G)=Θ(n). Builds an upper bound using a bit sampler that only queries when probabilities disagree, and introduces conflict complexity as a measure that is quadratically tight for partial G, connecting to communication lower bounds.
AI-written summary · about