The direct product problem is a fundamental question in complexity theory which seeks to understand how the difficulty of computing a function f on each of k independent inputs scales with k.

We prove a direct product theorem (DPT) for randomized query complexity which (roughly speaking) asserts the following: if every T-query algorithm has success probability at most (1 - eps) in computing the Boolean function f on input distribution D, then any algorithm making ~ eps T K queries has success probability not too much greater than (1-eps)^k in computing f correctly on K inputs sampled independently from D. In light of examples due to Shaltiel, our theorem provides an essentially optimal tradeoff between the query bound and the error probability. As a corollary, we show that the worst-case success probability of any (.01 R(f) k)-query randomized algorithm for the K-fold problem decays exponentially with K.

The proof involves defining and analyzing a collection of martingales associated with an algorithm attempting to solve the K-fold problem. Our method is quite general and yields a new XOR lemma and threshold DPT for the query model, as well as DPTs for the query complexity of learning tasks, search problems, and tasks involving interaction with dyamic entities.