Fall 2018

Strong Direct Sum for Randomized Query Complexity

Tuesday, October 16th, 2018 11:00 am11:30 am

Add to Calendar


Joshua Brody (Swarthmore College)

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.