Strong Direct Sum for Randomized Query Complexity
summary
Proves a strong direct sum for randomized query complexity with aborts: computing k independent copies with overall error epsilon requires Θ(k) times the queries needed for one copy with error ~epsilon/k, up to constant abort probability. The proof builds a query-resistant code that forces probing half a block, chains reductions from gap-identity → blue/red → pointer function → encoded function, and yields a family with query cost Θ(n m log 1/epsilon). The code is exponential in length, so the bound breaks down for exponentially small epsilon.
AI-written summary · about