loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2008 IEEE 23rd Annual Conference on Computational Complexity
A Direct Product Theorem for Discrepancy
June 22-June 26
ISBN: 978-0-7695-3169-4
Discrepancy is a versatile bound in communication complexity which can be used to show lower bounds in randomized, quantum, and even weakly-unbounded error models of communication. We show an optimal product theorem for discrepancy, namely that for any two Boolean functions f, g, disc(f xor g)=Theta(disc(f) disc(g)). As a consequence we obtain a strong direct product theorem for distributional complexity, and direct sum theorems for worst-case complexity, for bounds shown by the discrepancy method. Our results resolve an open problem of Shaltiel (2003) who showed a weaker product theorem for discrepancy with respect to the uniform distribution, disc_{U^k}(f^(k)) = O(disc_U(f))^(k/3). The main tool for our results is semidefinite programming, in particular a recent characterization of discrepancy in terms of a semidefinite programming quantity by Linial and Shraibman (2006).
Index Terms:
discrepancy, direct product theorems, direct sum theorems, communication complexity, factorization norms
Citation:
Troy Lee, Adi Shraibman, Robert ?palek, "A Direct Product Theorem for Discrepancy," ccc, pp.71-80, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008
Usage of this product signifies your acceptance of the Terms of Use.