Title: A Strong Direct Product Theorem for Discrepancy
Speaker: Troy Lee
Date: Wednesday, October 17, 2007 11:00-12:00pm
Location**: Hill Center, Room 254, Rutgers University, Busch Campus, Piscataway, NJ
**Please note location change
Abstract:
A strong direct product theorem states that if we err with probability 1/3 when computing a function f, then our advantage over random guessing in computing the parity of k independent instances of f will decrease exponentially, even given k times as many resources.
While intuitively it seems that we cannot hope to better, Shaltiel (2003) has given a general counterexample where a strong direct product theorems does not hold. He then studied a versatile lower bound technique in communication complexity, the discrepancy method, and showed a product theorem for discrepancy under the uniform distribution. An open question from this work was if a product theorem holds for discrepancy in general.
We answer this question in the positive, and improve the parameters of Shaltiel's result to give an optimal direct product theorem for discrepancy. This has application to a strong direct product theorem for distributional bounds proven by discrepancy and to direct sum theorems for randomized and quantum bounds shown by the discrepancy method. We will also discuss an interesting connection between discrepancy and XOR games.