2008 IEEE 23rd Annual Conference on Computational Complexity A Direct Product Theorem for Discrepancy June 22-June 26 ISBN: 978-0-7695-3169-4
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2008.25
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||