Abstract
In this talk, we consider randomized query complexity in the low-error regime, along with the direct sum problem for randomized query complexity. First, we give a total function whose \eps-error query complexity scales with log(1/\eps), even when the query algorithm is allowed to abort with constant probability. Asymptotic separations between zero-error and (1/3)-error query complexity for total functions weren't even known until very recently. We then give a strong direct sum theorem for randomized query complexity. Specifically, we show that computing k copies of any function f with error \eps requires k times the query complexity of computing one copy with low error (~ \eps/k) and constant abort probability. Taken together, these results give a total function f, such that computing k copies of f requires an Omega(k log k) blowup in query complexity, partially answering a question of Drucker [\cite{Drucker 12}] As a technical tool, we introduce the notion of a query resistant code, which is a probabilistic encoding ENC of an alphabet \Sigma such that at least half of the bits of ENC(x) must be queried before learning anything about x \in \Sigma.
This is joint work with Eric Blais.