[Colloquium] THEORY TALK TODAY: Andy Drucker

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, May 11, 2010
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------------------

Speaker:		Andy Drucker

From:		MIT, CSAIL

Web:		http://www.csail.mit.edu/user/1350  
  
Title: Improved Direct Product Theorems for Randomized Query Complexity

Abstract: 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100511/69102977/attachment.htm