Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0803.4206 · Lecture notes in computer science

Product Theorems Via Semidefinite Programming

Troy Lee, Rajat Mittal

Published Jan 1, 2008• 6 citations
arXivHTMLPDF
DOI
10.1007/978-3-540-70575-8_55

Related papers

Product Rules in Semidefinite Programming

Rajat Mittal, Márió Szegedy

Lecture notes in computer science•Aug 27, 2007•25 citations

Semidefinite programming and its applications to approximation algorithms

Thomas Hofmeister, Martin Hühne

Lecture notes in computer science•Jan 1, 1998•1 citation

Semidefinite programming and combinatorial optimization

Franz Rendl

Applied Numerical Mathematics•Mar 1, 1999•52 citations

Derivation of the Lewenstein–Sanpera Decomposition via Semidefinite Programming

M. A. Jafarizadeh, Mehdi Mirzaee, M. Rezaee

Quantum Information Processing•Aug 1, 2005•9 citations

Semidefinite programming from optimization to quantum chemistry

光浩 福田, Mituhiro Fukuda

•Jul 1, 2009•0 citations

A Direct Product Theorem for Discrepancy

Troy Lee, Adi Shraibman, Robert Špalek

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 odot g)=thetas(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, discUodot(fodotk)=O(discU(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).

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2008•84 citations
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 odot g)=thetas(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, discUodot(fodotk)=O(discU(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).