In recent years we witness the proliferation of semidefinite programming bounds in combinatorial optimization [1,5,8], quantum computing [9,2,3,6,4] and even in complexity theory [7]. Examples to such bounds include the semidefinite relaxation for the maximal cut problem [5], and the quantum value of multi-prover interactive games [3,4]. The first semidefinite programming bound, which gained fame, arose in the late seventies and was due to László Lovász [11], who used his theta number to compute the Shannon capacity of the five cycle graph. As in Lovász’s upper bound proof for the Shannon capacity and in other situations the key observation is often the fact that the new parameter in question is multiplicative with respect to the product of the problem instances. In a recent result R. Cleve, W. Slofstra, F. Unger and S. Upadhyay show that the quantum value of XOR games multiply under parallel composition [4]. This result together with [3] strengthens the parallel repetition theorem of Ran Raz [12] for XOR games. Our goal is to classify those semidefinite programming instances for which the optimum is multiplicative under a naturally defined product operation. The product operation we define generalizes the ones used in [11] and [4]. We find conditions under which the product rule always holds and give examples for cases when the product rule does not hold.
展开▼
机译：近年来，我们见证了半定规划界的增殖，组合优化[1,5,8]，量子计算[9,2,3,6,4]，甚至在复杂性理论[7]。这些界限的示例包括用于最大切割问题的半纤维弛豫[5]，以及多箴言交互式游戏的量子值[3,4]。第一个Semidefinite编程界定，它在七十年代末期获得了名望，并且是由于Lászlóvovász[11]，他们使用了他的Thea号码来计算五个周期图的香农容量。作为在香农容量Lovász的上限证明和在其他情况下重点观察往往是，有问题的新的参数是乘法相对于问题实例的产品。在最近的结果R.Cleve，W.Slofstra，F. Unger和S. Upadhyay表明，XOR游戏的量子值乘以并联组合物[4]。这结果与[3]加强了XOR游戏的RAN RAZ [12]的平行重复定理。我们的目标是将那些SemideFinite编程实例分类，其中最佳是在自然定义的产品操作下的乘法。我们定义的产品操作概括了[11]和[4]中使用的产品。我们发现在产品规则不持有的情况下，我们发现产品规则始终始终保持的条件，并为例举例说明。
展开▼
